Scale-free percolation mixing time (Q6145597): Difference between revisions

This paper is about the mixing time of a simple random walk on the so-called scale-free percolation random graph (SFP). This random graph \(G_{N}\) on which the random walk will take place is defined as follows: one takes vertex set \(\{1,2,\ldots N\}\) thought of as ordered round a circle. One assigns to each vertex \(i\) independently of all other vertices a weight \(W_{i}\), where \(W_{i}\) has a Pareto distribution with parameter \(\tau>1\), that is \(\mathbb{P}(W_{i}\geq t)=t^{-(\tau-1)}\) for \(t>1\) and is 1 otherwise. Note that this is a heavy-tailed distribution. We then say that two vertices \(x\) and \(y\) are adjacent with probability \(1-\exp(W_{x}W_{y}\left \| x-y \right \|^{-\alpha} )\). Here, the distance between \(x\) and \(y\), \(\left \| x-y \right\|\) is the torus distance between them i.e. \(\min \{\vert x-y\vert, N-\vert x-y\vert \}\). To ensure connectedness we also insist each vertex is adjacent to the one following it on the circle. There are thus two key parameters: \(\tau\) indicating how heavy-tailed the weights of the vertices are, and \(\alpha\) controlling how important the torus distance between the two vertices is to their chance of being adjacent. We put \(\gamma=\alpha (\tau-1)\), one can show that the degrees of vertices have a heavy-tailed distribution with parameter \(\gamma\). The simple random walk is a lazy one (to avoid periodicity issues): so the one-step transition matrix has \(P(x,x)=1/2\), if \(x\) and \(y\) are adjacent in the SFP we have \(P(x,y)=1/(2D_{x})\) where \(D_{x}\) is the degree of \(x\), and if \(x\) and \(y\) are not adjacent \(P(x,y)=0\). As usual we are interested in the mixing time \(t_{mix}(G_{N})=\inf \{n\in \mathbb{N}: d(n) < \frac{1}{4}\}\) where \(d(n)=\sup_{x\in \{1,2,\ldots N\}} \left \| P^{n}(x,\cdot)-\pi(\cdot) \right \|_{TV}\) where as usual the total variation distance \(\left \| \nu-\mu\right \|_{TV}\) between distirbutions \(\nu\) and \(\mu\) is \(\frac{1}{2}\sum_{x\in [n]}\vert \nu(x)-\mu(x)\vert\). Important background to the results in this paper is [\textit{I. Benjamini} et al., Comb. Probab. Comput. 17, No. 4, 487--494 (2008; Zbl 1157.60084)] where the analogous problem is studied on the long-range percolation graph, which is the case where all weights \(W_{i}\) are equal to one (in essence, the case \(\tau=\infty\)). In that paper there is a striking phase transition around \(\alpha=2\): for \(1<\alpha<2\) we have mixing time (up to polylogarithmic factors) \(N^{\alpha-1}\) but for \(\alpha>2\) the mixing time (up to polylogarithmic factors) is \(N^{2}\). The authors show an almost complete phase diagram for both parameters \(\alpha\) and \(\tau\). To give some flavour of the results, and noting that results are only stated up to correcting factors, for example is it shown that in the first significant case when \(\gamma<1\) we have \(t_{\mathrm{mix}}(G_{N})\) is bounded above by a power of \(\log(N)\). In the second, perhaps most interesting, regime \(1<\gamma<2\) and \(\tau<2\), \(t_{\mathrm{mix}}(G_{N})\) is of order \(N^{\gamma-1}\) and the proof depends on a bootstrapping procedure to relate it to a model with \(\gamma<1\). Here, the presence of hubs (vertices of very high degree) can speed out the mixing. The third case is \(\alpha \in (1,2)\) and \(\tau>2\) where the authors can only show that \(t_{\mathrm{mix}}(G_{N})\) is of order at least \(N^{\alpha-1}\) though they conjecture that a similar upper bound holds up to polylogarithmic factors and give some supporting evidence. The fourth case is \(\alpha>2\) and \(\gamma>2\) when \(t_{\mathrm{mix}}(G_{N})\) is of order \(N^{2}\). A substantial range of techniques have to be used to cover all the various results proven.