Shepp, Larry2023-05-232023-05-231989-02-012016-07-11https://repository.upenn.edu/handle/20.500.14332/47944L. Dubins conjectured in 1984 that the graph on vertices {1, 2, 3, ...} where an edge is drawn between verticesi andj with probability pij=λ / max(i, j) independently for each pairi andj is a.s. connected for λ=1. S. Kalikow and B. Weiss proved that the graph is a.s. connected for any λ>1. We prove Dubin’s conjecture and show that the graph is a.s. connected for anyλ>1/4. We give a proof based on a recent combinatorial result that forλ ≦ 1/4 the graph is a.s. disconnected. This was already proved for λ < 1/4 by Kalikow and Weiss. Thus λ= 1/4 is the critical value for connectedness, which is surprising since it was believed that the critical value is at λ=1.The final publication is available at Springer via http://dx.doi.org/10.1007/BF02764896.Statistics and ProbabilityArticle