On a Question of Benjamini on First-Passage Percolation in Hierarchical Graphs: The Recursive Constant Exceeds the Branching Random Walk Constant

In Question 9.1 of his survey “Euclidean vs. Graph Metric” (2013), Benjamini considers first-passage percolation on the hierarchical graphs \(G_n\) obtained by replacing, recursively, every edge by one edge followed by two parallel edges. With independent positive edge weights of law \(\xi\), the source–sink distance satisfies \(D_n\overset{d}{=} D_{n-1}+\min(D_{n-1}',D_{n-1}'')\). The question asks to compute \(\gamma_{\mathrm{rec}}=\lim 2^{-n}\mathbb{E} D_n\) in terms of \(\xi\), and in particular to show, if true, that \(\gamma_{\mathrm{rec}}>\gamma_{\mathrm{brw}}\), the speed of the minimal position of the binary branching random walk with step law \(\xi\), which is a lower bound for \(\gamma_{\mathrm{rec}}\). We give a partial answer. We prove \(\gamma_{\mathrm{rec}}>\gamma_{\mathrm{brw}}\) for every non-degenerate law \(\xi\) that is bounded below and has finite mean, hence for every non-degenerate law of positive weights with finite mean. The proof is a standard first-moment (union) bound taken one level up the hierarchy, combined with the inequality \(e^{-t\min(x,y)}<e^{-tx}+e^{-ty}\); at level zero the first-moment bound is \(\gamma_{\mathrm{brw}}\), by the classical theorem of Hammersley, Kingman and Biggins. We also show that \(\gamma_{\mathrm{rec}}\) is the increasing limit of explicit first-moment bounds and the decreasing limit of \(2^{-k}\mathbb{E} D_k\), that \(D_n/2^n\to\gamma_{\mathrm{rec}}\) in \(L^1\), as anticipated in the source, and that \(2^{-k}\mathbb{E} D_k-\gamma_{\mathrm{rec}}\le\frac{1+\sqrt2}{2}\,\|\xi-\operatorname*{ess\,inf}\xi\|_2\,2^{-k/2}\). Certified computer-assisted computations give \(\gamma_{\mathrm{rec}}\in[0.268785599,\,0.268808710]\) for weights uniform on \([0,1]\), where \(\gamma_{\mathrm{brw}}=0.18482\ldots\), and \(\gamma_{\mathrm{rec}}\in[0.379282228,\,0.379412906]\) for exponential weights of mean one, where \(\gamma_{\mathrm{brw}}=0.23196\ldots\); in particular, the remark in the UnsolvedMath collection that the two constants coincide in the exponential case is incorrect. A closed formula for \(\gamma_{\mathrm{rec}}\) in terms of \(\xi\), the “compute” part of the question, remains open. The method is standard; no answer to the question was found in the literature accessible to us, and no priority is claimed. This is an unrefereed note.