July 01, 2026
We study a dynamic averaging process on the cycle \(C_n\). At each discrete time, an edge is chosen uniformly at random, one unit of load is introduced, and the two endpoint loads are replaced by their common average after the new unit has been added. Starting from the zero configuration, we prove that the expected gap between the largest and smallest loads is \(O(\sqrt n)\), uniformly in time. Building on the lower-bound argument of Alistarh, Nadiradze, and Sabour for the expected square of the gap, we further show that the expected gap is \(\Omega(\sqrt n)\) in the long run. This confirms their conjecture that the expected gap is of order \(\sqrt n\).
Keywords: Dynamic Averaging, Load Balancing, Cycle Graphs, Moment-Generating Function, Dyadic Chaining.
Randomized load balancing has its origins in the classical balls-into-bins model. In the classical \(d\)-choice process, \(m\) balls are inserted sequentially into \(n\) bins, and each ball is placed in the least loaded among \(d\) bins chosen uniformly at random. Azar, Broder, Karlin, and Upfal [1] showed that, when \(m=n\), the maximum load is \(\Theta\left(\frac{\log\log n}{\log d}\right)\) with high probability, a dramatic improvement over the \(\Theta(\log n/\log\log n)\) maximum load obtained with a single random choice.
Berenbrink, Czumaj, Steger, and Vöcking [2] extended this result to the heavily loaded regime \(m=\omega(n)\), proving that the maximum load is \(\frac{m}{n} + \frac{\log\log n}{\log d} + O(1)\) with high probability. Peres, Talwar, and Wieder [3] subsequently studied graphical balanced allocations, in which a randomly selected edge determines the two possible destinations of each arriving load item. To our knowledge, the current best known upper bound for this process on cycle graphs is given by [3], and is \(O(n \log(n))\).
A closely related line of work studies averaging processes, in which neighboring vertices repeatedly redistribute their loads rather than assigning each new item to a single vertex. In the static setting, where no new load arrives during the process, the rate of convergence is closely connected to the mixing behavior of the underlying graph. Sauerwald and Sun [4] obtained strong discrepancy bounds for the discrete version of this process on a large family of graphs.
The dynamic setting is more delicate, particularly on slowly mixing graphs such as the cycle. Alistarh, Nadiradze, and Sabour [5] proved that on an \(n\)-vertex cycle the expected gap is \(O(\sqrt n\log n)\). They also established the lower bound \(\mathbb{E}[\operatorname{Gap}(t)^2]=\Omega(n)\), for sufficiently large \(t\), and provided empirical evidence that the correct order of the expected gap should be \(\sqrt n\). Subsequently, Berenbrink, Hintze, Hosseinpour, Kaaser, and Rau [6] improved the upper bound for the cycle to \(O(\sqrt{n\log n})\).
In this work, we improve the upper bound further, and show that the expected gap is \(O(\sqrt n)\). We then use the lower bound established in [5] to show that the lower bound of the expected gap is indeed \(\Omega(\sqrt n)\) for sufficiently large \(t\). This provides an affirmative answer to the conjecture posed by the authors that the expected gap is of order \(\sqrt n\).
Let \(C_n\) be the cycle graph with vertex set \(V(C_n)=\mathbb{Z}/n\mathbb{Z}\) and edge set \(E(G)= \{\{i,i+1\}: i \in \mathbb{Z}/n\mathbb{Z}\}\) (throughout indices are understood to be modulo \(n\)). We consider the following dynamic averaging process: at every discrete time \(t\), one edge of the cycle is selected uniformly at random. The total load of the two selected endpoints, together with one new unit, is divided equally between them. Thus, if the selected edge is \(\{i,i+1\},\) then the two endpoint loads are updated according to \[x_i(t+1) = x_{i+1}(t+1) = \frac{x_i(t)+x_{i+1}(t)+1}{2}.\] All other loads remain unchanged. We assume throughout that the initial configuration is flat: \(x_i(0)=0 \; \text{for every }i\in V(C_n).\) The quantity of interest is the load gap \[\operatorname{Gap}(t) := \max_{i\in V(C_n)}x_i(t) - \min_{i\in V(C_n)}x_i(t).\]
The main results are presented in the following Theorems:
Theorem 1. There exists a universal constant \(C\) such that for every \(n\ge 3\) and every \(t\ge 0\), \[\mathbb{E}[\operatorname{Gap}(t)] \le C\sqrt n.\]
Theorem 2. There exists a universal constant \(c>0\) such that for every \(n\ge 3\) and every sufficiently large3 \(t\ge 0\), \[\mathbb{E}[\operatorname{Gap}(t)] \ge c\sqrt n.\]
Let \(\{x_i(t)\}_{i \in V(C_n)}\) be the loads of each vertex at time \(t\). We denote the centered load vector \(X(t) = \bigl(X_0(t),\ldots,X_{n-1}(t)\bigr)^\mathsf T,\) where \(X_i(t) = x_i(t)-\frac{t}{n}.\) One can verify that \(\sum_{i=0}^{n-1}X_i(t)=0.\) and, \(\operatorname{Gap}(t) = \max_iX_i(t)-\min_iX_i(t).\)
Let \(e_i\) be the \(i\)-th standard basis vector in \(\mathbb{R}^n\). For each edge \(\{i,i+1\},\) we define \[A_i := I-\frac{1}{2} (e_i-e_{i+1})(e_i-e_{i+1})^{\mathsf T}.\] The matrix \(A_i\) averages coordinates \(i\) and \(i+1\), indeed, \((A_iz)_i = (A_iz)_{i+1} = \frac{z_i+z_{i+1}}{2}.\)
We also define \[c_i := \frac{1}{2}(e_i+e_{i+1}) - \frac{1}{n}\mathbf{1},\] where \(\mathbf{1}=e_1+...+e_n\). Note that if at time \(t\) the edge \(\{i,i+1\}\) is selected, then \[X(t+1) = A_iX(t)+c_i.\] Indeed, \(X_{i+1}(t+1)=X_i(t+1)=\frac{X_i(t)+X_{i+1}(t)}{2} +\frac{1}{2}-\frac{1}{n},\) while all other entries decrease by \(\frac{1}{n}\).
Fix \(\theta=(\theta_0,\ldots,\theta_{n-1})\in\mathbb{R}^n,\) and denote the moment generating function \[M_t(\theta) := \mathbb{E}\left[\exp\bigl(\left\langle \theta,X(t)\right\rangle\bigr)\right],\] where \(\left\langle \theta,X(t)\right\rangle =\theta ^ \mathsf T X(t)= \sum_{j=0}^{n-1}\theta_jX_j(t)\) denotes the standard inner product. We wish to use chernoff bound to give a bound for the upper tails. Our primary goal is thus to bound the moment generating function uniformly in \(t\).
Lemma 1. For every \(\theta\in\mathbb{R}^n\), \[M_{t+1}(\theta) = \frac{1}{n} \sum_{i=0}^{n-1} \exp\bigl(\left\langle \theta,c_i\right\rangle\bigr) M_t(A_i\theta).\]
Proof. If the edge \(\{i,i+1\}\) was selected at time \(t\), then \[\left\langle \theta,X(t+1)\right\rangle = \left\langle \theta,A_iX(t)+c_i\right\rangle \underset{(*)}{=} \left\langle A_i\theta,X(t)\right\rangle + \left\langle \theta,c_i\right\rangle.\] Where the equality marked \((*)\) comes from the fact \(A_i\) is symmetric. Averaging on the edges gives the desired Lemma. ◻
Adding a multiple of \(\mathbf{1}\) to a vector \(\theta\) does not change \(\left\langle \theta,X(t)\right\rangle,\) therefore we restrict to vectors satisfying \(\sum_i\theta_i=0.\)
Definition 1. Let \(\theta\in\mathbb{R}^n\) such that \(\sum_i\theta_i=0.\) The mean-zero cyclic primitive of \(\theta\) is a vector \(f=(f_0,\ldots,f_{n-1})\) such that \[\theta_i=f_i-f_{i-1}, \text{ for every } i \qquad \text{and} \qquad \sum_{i}f_i =0.\]
The mean-zero primitive can be explicidly constructed \(f_i = \theta_1+\dots +\theta_i -\frac{1}{n} \sum_{j=1}^{n-1}(n-j)\theta_j \;, \;i =0,1,...,n-1.\)
Let \(f\) be the mean-zero primitive of \(\theta\). Define \[R(\theta) := \sum_{i=0}^{n-1}f_i^2 - \frac{1}{2n} \sum_{i=0}^{n-1}\theta_i^2.\] The factor \(\frac{1}{2n}\) will be essential for a cancellation property that occurs after applying \(A_i\).
We first notice that \(R\) is nonnegative. Indeed, since \((x-y)^2 \le 2x^2+2y^2\) we deduce \[R(\theta)=\sum_{i=0}^{n-1}f_i^2 - \frac{1}{2n} \sum_{i=0}^{n-1}\theta_i^2 \ge \sum_{i=0}^{n-1}f_i^2 - \frac{1}{2n} \sum_{i=0}^{n-1}2(f_i^2 +f_{i-1}^2)=\left(1-\frac{2}{n}\right)\sum_{i=0}^{n-1}f_i^2\ge 0.\] We now define a class of test vectors that is preserved by the operators \(A_i\).
Definition 2. Fix \(a>0\). Let \(\mathcal{U}_a\) be the collection of zero-sum vectors \(\theta\in\mathbb{R}^n\) satisfying the following conditions.
After all zero coordinates are removed from the cyclic sequence \(\theta_0,\theta_1, \ldots,\theta_{n-1},\) the signs change at most twice. Equivalently, the nonzero coordinates consist of one positive cycle interval and one negative cycle interval.
If \(f\) is the mean-zero primitive of \(\theta\), then \(\operatorname{osc}(f) := \max_i f_i-\min_i f_i \le a.\)
The main motivation behind this definition is the following Theorem:
Theorem 3. For every \(t\ge0\) and every \(\theta\in\mathcal{U}_{1/32},\) we have \[M_t(\theta) \le \exp\bigl(4R(\theta)\bigr).\]
We show how from Theorem 3 follows the desired square root upper bound on the gap.
Let \(a,b\in V(C_n)\). Their graph distance is given by \(d(a,b) = \min\{|a-b|,n-|a-b|\}.\) For a scalar \(s\in\mathbb{R}\), we choose \(\theta = s(e_b-e_a)\in\mathcal{U}_{|s|},\) and notice that \(\left\langle \theta,X(t)\right\rangle = s\bigl(X_b(t)-X_a(t)\bigr).\)
Lemma 2. Let one arc from \(a\) to \(b\) have length \(r\). Then \[R\bigl(s(e_b-e_a)\bigr) = s^2 \frac{r(n-r)-1}{n}.\] In particular, \[R\bigl(s(e_b-e_a)\bigr) \le s^2d(a,b).\]
Proof. The primitive of \[s(e_b-e_a)\] is constant on one arc from \(a\) to \(b\) and constant on its complement. The two constant values differ by \(s\).
If the first arc has \(r\) vertices and the complementary arc has \(n-r\) vertices, the mean-zero values are, up to interchanging the two arcs, \[s\frac{n-r}{n} \qquad \text{and} \qquad -s\frac{r}{n}.\]
Therefore, \(\begin{aligned} \sum_i f_i^2 &= r \left( s\frac{n-r}{n} \right)^2 + (n-r) \left( s\frac{r}{n} \right)^2 = s^2\frac{r(n-r)}{n}, \end{aligned}\) and, \(\sum_i\theta_i^2 = 2s^2.\)
Thus \[\begin{align} R\bigl(s(e_b-e_a)\bigr) &= s^2\frac{r(n-r)}{n} - \frac{1}{2n}(2s^2) = s^2\frac{r(n-r)-1}{n}. \end{align}\] ◻
We show an sub-Gaussian pairwise tail. More precisely, we show sub-Gaussian concentration up to the distance scale
Theorem 4. There exist universal constants \(c,C>0\) such that, for every \(n\ge3\), every \(t\ge0\), every distinct \(a,b\in V(C_n)\), and every \(u\ge0\), \[\Pr\left( |X_b(t)-X_a(t)|\ge u \right) \le C \exp\left( -c \min\left\{ \frac{u^2}{d(a,b)}, u \right\} \right).\]
Proof. Assume \(a\ne b,\) and write \(d=d(a,b).\) For every \(0\le s\le\frac{1}{32},\) we have \(s(e_b-e_a) \in \mathcal{U}_{1/32}.\) By Theorem 3 and Lemma 2, \[\mathbb{E} \exp\left( s(X_b(t)-X_a(t)) \right) \le \exp(4s^2d).\] By Markov’s inequality/Chernoff’s bound, \[\begin{align} \Pr\left( X_b(t)-X_a(t)\ge u \right) &= \Pr\left( e^{s(X_b(t)-X_a(t))} \ge e^{su} \right)\\ &\le e^{-su} \mathbb{E}e^{s(X_b(t)-X_a(t))}\\ &\le \exp(-su+4s^2d). \end{align}\]
Suppose first that \(u\le\frac{d}{4}.\) Choose \(s=\frac{u}{8d},\) and notice \(s\le\frac{1}{32},\) and \(-su+4s^2d = -\frac{u^2}{8d} + 4\frac{u^2}{64d}= -\frac{u^2}{16d}.\)
Suppose now that \(u>\frac{d}{4}.\) Choose \(s=\frac{1}{32},\) and notice \(d<4u,\) and therefore \(-su+4s^2d = -\frac{u}{32} + \frac{d}{256}\le -\frac{u}{32} + \frac{u}{64} = -\frac{u}{64}.\)
The same argument applied to \(X_a(t)-X_b(t)\) gives the lower-tail bound. Combining the two tails proves the theorem. ◻
We show the following standard consequence of sub-Gaussian variables (e.g. Theorem 3.1.10 in [7] ,Proposition 2.7.6 in [8]).
Lemma 3. Let \(Y_1,\ldots,Y_N\) be random variables, not necessarily independent, satisfying \[\Pr(|Y_j|\ge u) \le 2 \exp\left( -c \min\left\{ \frac{u^2}{L}, u \right\} \right)\] for every \(j\) and every \(u\ge0\). Then \[\mathbb{E}\max_{1\le j\le N}|Y_j| \le C \left( \sqrt{L\log(2N)} + \log(2N) \right),\] where \(C\) depends only on \(c\).
Proof. By the union bound, \[\Pr\left( \max_j|Y_j|\ge u \right) \le 2N \exp\left( -c \min\left\{ \frac{u^2}{L}, u \right\} \right)= \exp\left(\log(2N) -c \min\left\{ \frac{u^2}{L}, u \right\}\right).\] Notice that \[\min\left\{ \frac{(\sqrt{Ly}+y)^2}{L}, \sqrt{Ly}+y \right\} \ge y\] holds for every \(y\ge0\). Thus, for a sufficiently large constant \(c'\), and for \(x\ge0\) taking \[u_x = c' \left( \sqrt{L(\log(2N)+x)} + \log(2N)+x \right),\] we get that \(c \min\left\{ \frac{u_x^2}{L}, u_x \right\} \ge \log(2N)+x,\) by taking \(y = \log(2N)+x.\) It follows that \[\Pr\left( \max_j|Y_j|\ge u_x \right) \le e^{-x}.\]
Integrating this exponential tail yields \[\mathbb{E}\max_j|Y_j| = \int_0^\infty \Pr(\max_j |Y_j| \ge u)\,du = \int_0^{u_0} \Pr(\max_j |Y_j| \ge u)\,du+\int_{u_0}^\infty \Pr(\max_j |Y_j| \ge u)\,du \le\] \[u_0+\int_{u_0}^\infty \Pr(\max_j |Y_j| \ge u)\,du \underset{u=u_x}{=} u_0+\int_{0}^\infty \Pr(\max_j |Y_j| \ge u_x)u_x' \,dx \le u_0+\int_{0}^\infty e^{-x} u_x' \,dx =\] \[u_0 + \int_0^\infty c' e^{-x} \left(\frac{\sqrt L}{2\sqrt{\log(2N)+x}} +1\right) \le u_0 + c' \left(\frac{\sqrt L}{2\sqrt{\log(2N)}} +1\right)\int_0^\infty e^{-x} \,dx =\] \[c' \left( \sqrt{L\log(2N)}+\log(2N) \right)+c' \left(\frac{\sqrt L}{2\sqrt{\log(2N)}} +1\right) \le C\left( \sqrt{L\log(2N)}+\log(2N) \right).\] ◻
Let \(m=\lceil\log_2n\rceil.\) For each \(0\le k\le m,\) choose a set \(T_k\subseteq V(C_n)\) such that \(T_0=\{o\},T_m=V(C_n)\) for some fixed root \(o\), and \(|T_k|\le2^k\). The points of \(T_k\) may be chosen approximately evenly spaced around the cycle. In this manner for each \(i\in T_k,\) we may choose a parent \(\mathrm{par}_k(i)\in T_{k-1}\) that minimizes the graph distance to \(i\), and in particular \(d\bigl(i,\mathrm{par}_k(i)\bigr) \le C\frac{n}{2^k}.\)
Define \[Z_k(t) = \max_{i\in T_k} \left| X_i(t)-X_{\mathrm{par}_k(i)}(t) \right|.\]
Lemma 4. There exists a universal constant \(C\) such that \[\mathbb{E}Z_k(t) \le C \left( \sqrt{\frac{n(k+1)}{2^k}} + k+1 \right)\] for every \(1\le k\le m\) and every \(t\ge0\).
Proof. There are at most \(|T_k|\le2^k\) parent links at level \(k\). Each link has length at most \(L_k = C\frac{n}{2^k}.\) By Theorem 4, every parent increment satisfies an sub-Gaussian tail with scale \(L_k\). Applying Lemma 3 with \(N\le2^k\) gives \[\begin{align} \mathbb{E}Z_k(t) &\le C \left( \sqrt{ \frac{n}{2^k} \log(2^{k+1}) } + \log(2^{k+1}) \right) \le C \left( \sqrt{\frac{n(k+1)}{2^k}} + k+1 \right). \end{align}\] ◻
Proof of Theorem 1. Fix the root \(o\in T_0.\) Every vertex \(i\in T_m=V(C_n)\) is connected to \(o\) by following its sequence of parents through the sets \(T_m,T_{m-1},\ldots,T_0.\) By the triangle inequality, \[|X_i(t)-X_o(t)| \le \sum_{k=1}^{m}Z_k(t).\] Thus taking the maximum over \(i\), and then expectation, we get using Lemma 4, \[\mathbb{E}\max_i|X_i(t)-X_o(t)| \le C \sum_{k=1}^{m} \sqrt{\frac{n(k+1)}{2^k}} + C \sum_{k=1}^{m}(k+1) \le C\sqrt n \sum_{k=1}^{\infty} \sqrt{\frac{k+1}{2^k}} + Cm^2 \le C \sqrt n +C(\log n)^2.\] It follows that \[\mathbb{E}\max_i|X_i(t)-X_o(t)| \le C\sqrt n.\] Finally, \[\mathbb{E}[\operatorname{Gap}(t)] = \mathbb{E}[\max_iX_i(t)-\min_iX_i(t)]\le 2\mathbb{E}[\max_i|X_i(t)-X_o(t)|] \le C \sqrt n.\] ◻
The remaining part of the proof of the upper bound is dedicated to prove Theorem 3.
Lemma 5. For every \(a>0\) and every \(i\), we have \(A_i\mathcal{U}_a \subseteq \mathcal{U}_a.\)
Proof. Let \(\theta \in \mathcal{U}_a\). Recall that the operator \(A_i\) replaces the adjacent pair \(\theta_i,\theta_{i+1}\) by their common average \(\frac{\theta_i+\theta_{i+1}}{2}.\) One may verify that \(A_i\theta\) still consists of at most one positive interval and at most one negative intervals separated by zeros.
We now consider the range of the primitive. Let \(f\) be the mean-zero primitive of \(\theta\). Notice that the mean-zero cyclic primitive of \(A_i\theta\) is given by \[f'_j = f_j+\varepsilon \quad (j \neq i), \qquad f'_i = \frac{f_{i-1}+f_{i+1}}{2}+\varepsilon.\] where \(\varepsilon = \frac{1}{n} (f_i - \frac{f_{i-1}+f_{i+1}}{2})\) is some error term to guarantee \(f'\) has zero sum. Indeed, \(f'_i-f'_{i-1} = \frac{f_{i+1}-f_{i-1}}{2} = \frac{\theta_i+\theta_{i+1}}{2},\) and \(f'_{i+1}-f'_i = \frac{f_{i+1}-f_{i-1}}{2} = \frac{\theta_i+ \theta_{i+1}}{2}.\)
One may verify that \(\operatorname{osc}(f')\le \operatorname{osc}(f)\le a\). Thus all together \(A_i\theta \in \mathcal{U}_a\). ◻
Definition 3. Fix \(\theta\in\mathcal{U}_a,\) and let \(f\) be its mean-zero primitive. For each edge \(\{i,i+1\}\), define \[z_i := \left\langle \theta,c_i\right\rangle.\] Also define \[q_i := R(A_i\theta)-R(\theta).\]
It will become clear why we are interested in this objects in the proof of Proposition 5. We now calculate these quantities explicitly.
Recall \(c_i = \frac{1}{2}(e_i+e_{i+1}) - \frac{1}{n}\mathbf{1}.\) We obtain \[z_i = \frac{\theta_i+\theta_{i+1}}{2} = \frac{f_{i+1}-f_{i-1}}{2}.\] In particular we notice that if \(\operatorname{osc}(f)\le a,\) then \(|z_i|=\frac{|f_{i+1}-f_{i-1}| }{2}\le\frac{a}{2}.\)
The calculation of \(q_i\) is the point at which the factor \(\frac{1}{2n}\) in the definition of \(R\) becomes essential. Denote \(m_i = \frac{f_{i-1}+f_{i+1}}{2}\). Recall as in the proof of Lemma 5 that the mean-zero primitive of \(A_i\theta\) is given by \[f'_j = f_j+\varepsilon \quad (j \neq i), \qquad f'_i = \frac{f_{i-1}+f_{i+1}}{2}+\varepsilon.\] where \(\varepsilon = \frac{1}{n} (f_i - \frac{f_{i-1}+f_{i+1}}{2})=\frac{1}{n} (f_i-m_i)\). We now compute the change in the first term of \(R\). We have \[\sum_j(f'_j)^2-\sum_jf_j^2 =\sum_{j\neq i} (f_j+\varepsilon )^2 - \sum_{j\neq i} f_j^2 +(m_i+\varepsilon)^2-f_i^2=\] \[m_i^2-f_i^2+n\varepsilon^2 +2\varepsilon \bigl(\sum_{j\neq i}f_j+m_i \bigr)=m_i^2-f_i^2+n\varepsilon^2 +2\varepsilon(-f_i+m_i)= m_i^2-f_i^2-n\varepsilon^2.\]
Next we compute the change in the second term of \(R\). Only \(\theta_i\) and \(\theta_{i+1}\) are modified. Thus \[\begin{align} \sum_j(A_i\theta)_j^2-\sum_j\theta_j^2 &= 2 \left( \frac{\theta_i+\theta_{i+1}}{2} \right)^2 - \theta_i^2-\theta_{i+1}^2 = -\frac{1}{2} (\theta_i-\theta_{i+1})^2. \end{align}\]
On the other hand, \[n\varepsilon = f_i-m_i = \frac{2f_i-f_{i-1}-f_{i+1}}{2} = \frac{(f_i-f_{i-1})-(f_{i+1}-f_i)}{2} = \frac{\theta_{i}-\theta_{i+1}}{2}.\] Hence \(\sum_j(A_i\theta)_j^2-\sum_j\theta_j^2 = -2n^2 \varepsilon^2.\) Therefore \[q_i = R(A_i\theta)-R(\theta) = \left( m_i^2-f_i^2-n\varepsilon^2 \right) - \frac{1}{2n} \left( -2n^2\varepsilon^2 \right) = m_i^2-f_i^2.\]
This subsection, which is divided into several technical Lemmas, is dedicated to show a particular cancellation property of \(q_i,z_i\). Namely that \[\sum_i (z_i+4q_i)+\sum_i (z_i+4q_i)^2 \le0.\] This will be the main tool in the proof of Proposition 5.
Lemma 6. For every \(\theta\in\mathcal{U}_a,\) we have \[\sum_iq_i = -\sum_i z_i^2.\]
Proof. Using the previously established explicit form of \(z_i,q_i\) we obtain \[q_i+z_i^2 = \left( \frac{f_{i-1}+f_{i+1}}{2} \right)^2 -f_i^2 + \left( \frac{f_{i+1}-f_{i-1}}{2} \right)^2 = \frac{f_{i-1}^2+f_{i+1}^2}{2} -f_i^2.\] Summing over \(i\), we get 0 \[\sum_i(q_i+z_i^2)=\sum_i \frac{f_{i-1}^2+f_{i+1}^2}{2} - \sum_i f_i^2=0.\] ◻
We next prove an inequality that uses the sign-block structure of \(\theta\).
Lemma 7. Let \(\theta\in\mathbb{R}^n\) have zero sum, and assume that, after zero entries are removed, the signs of the cyclic sequence \((\theta_i)\) change at most twice. Then \[\sum_i(\theta_{i+1}-\theta_i)^2 \le 5 \sum_i(\theta_{i+1}+\theta_i)^2.\]
Proof. Set \[A = \sum_i\theta_i^2, \qquad B = \sum_i\theta_i\theta_{i+1}.\] If \(\theta=0\), there is nothing to prove. We therefore assume that both positive and negative entries occur.
Notice that negative elements of the form \(\theta_i\theta_{i+1}\) can occur at most twice in \(B\). Assume that both the positive cycle interval and the negative cycle interval have at least two nonzero elements. Since \(|xy|\le \frac{x^2+y^2}{2}\) and since both intervals have at least two nonnegative elements, the four coordinates appearing in the negative products are distinct. Thus, \(B\ge -\frac{1}{2} A\).
Suppose that one sign block consists of a single elements. Without loss of generality, assume its the positive block, which consists of a single value \(\theta_i>0.\) Let \(s= |\theta_{i-1}|+|\theta_{i+1}|\). Since \(\theta\) has zero sum, \(s\le \theta_i.\)
Notice \(\theta_is \le\frac{2}{3} \left( \theta_i^2+\frac{s^2}{2} \right)\), as \(2\theta_i^2-3\theta_i s+s^2 = (2\theta_i-s)(\theta_i-s) \ge0.\) Also, \(\frac{s^2}{2} \le \theta_{i-1}^2+\theta_{i+1}^2 \le \sum_{j\neq i}\theta_j^2\), and therefore \(\theta_i s \le \frac{2}{3}A\). Since \(B\) has at most two negative elements, we notice \(B \ge -\theta_is\), so from the above we deduce \(B \ge -\frac{2}{3} A\).
All together \[\sum_i(\theta_{i+1}-\theta_i)^2 = 2(A-B) \le 10(A+B) = 5\sum_i(\theta_{i+1}+\theta_i)^2.\] ◻
Lemma 8. For every \(\theta\in\mathcal{U}_a,\) we have \[\sum_iq_i^2 \le 20a^2 \sum_i z_i^2.\]
Proof. Let \(f\) be the mean-zero primitive of \(\theta\). Since \(f\) has zero sum, \(\min_j f_j \le 0 \le \max_j f_j\). In particular, for every \(i\) we get \[|f_i| \le \max(\max_i f_i , - \min_i f_i ) \le \max_i f_i - \min_i f_i \le a.\]
Recall that we defined \(m_i = \frac{f_{i-1}+f_{i+1}}{2}\), and thus we also have \(|m_i|\le a.\)
Therefore, \[q_i^2=(m_i^2-f_i^2)^2 = (m_i-f_i)^2(m_i+f_i)^2 \le (m_i-f_i)^2(|m_i|+|f_i|)^2 \le\] \[4a^2(m_i-f_i)^2 = 4a^2 \left(\frac{\theta_{i+1}-\theta_i}{2}\right)^2 = a^2 (\theta_{i+1}-\theta_i)^2\] Summing over \(i\) and applying Lemma 7, \[\sum_iq_i^2 \le 5a^2 \sum_i(\theta_{i+1}+\theta_i)^2=20a^2 \sum_i z_i^2.\] ◻
Proposition 5. For every \(\theta\in\mathcal{U}_{\frac{1}{32}},\) we have \[\frac{1}{n} \sum_{i=0}^{n-1} \exp\left( \left\langle \theta,c_i\right\rangle + 4\bigl(R(A_i\theta)-R(\theta)\bigr) \right) \le1.\]
Proof. By Lemma 6, \[\sum_i z_i+4q_i = 0 + 4\sum_iq_i = -4\sum_i z_i^2.\]
Also, since \((x+y)^2\le2x^2+2y^2,\) we have \[\sum_i (z_i+4q_i)^2 \le 2\sum_i z_i^2 + 32\sum_iq_i^2.\] By Lemma 8, \[\sum_i (z_i+4q_i)^2 \le \left( 2+640\left(\frac{1}{32}\right)^2 \right) \sum_i z_i^2 \le 4\sum_i z_i^2.\] Consequently, \[\sum_i (z_i+4q_i)+\sum_i (z_i+4q_i)^2 \le0.\] We notice that since \(\operatorname{osc}(f)\le \frac{1}{32},\) for every \(i\) we have \(|z_i|\le\frac{\operatorname{osc}(f)}{2}=\frac{1}{64}.\) Moreover, \(|q_i| = |m_i^2-f_i^2| \le \frac{1}{32}^2.\) It follows that \(|z_i+4q_i| \le \frac{1}{64}+4\frac{1}{32}^2 <1.\)
Using the fact that \(e^{x}\le1+x+x^2\) for any \(|x|\le 1\), and then summing over \(i\), \[\sum_i e^{z_i+4q_i} \le \sum_i(1+(z_i+4q_i)+(z_i+4q_i)^2)\\ \le n.\] ◻
We are now ready to prove Theorem 3.
Proof of Theorem 3. We proceed by induction on \(t\).
At time \(0\), \(X(0)=0.\) By nonegativity of \(R\) we indeed get \(M_0(\theta)=1 \le \exp\bigl(4R(\theta)\bigr).\)
Assume that the result holds at time \(t\). By Lemma 1, \[M_{t+1}(\theta) = \frac{1}{n} \sum_i \exp\bigl(\left\langle \theta,c_i\right\rangle\bigr) M_t(A_i\theta).\]
By Lemma 5, \(A_i\theta\in\mathcal{U}_{1/32}.\) Hence the induction hypothesis gives \(M_t(A_i\theta) \le \exp\bigl(4R(A_i\theta)\bigr).\) It follows that \[M_{t+1}(\theta) \le \frac{1}{n} \sum_i \exp\left( \left\langle \theta,c_i\right\rangle + 4R(A_i\theta) \right) = \exp\bigl(4R(\theta)\bigr) \frac{1}{n} \sum_i \exp\left( \left\langle \theta,c_i\right\rangle + 4\bigl(R(A_i\theta)-R(\theta)\bigr) \right).\] The right hand side average is at most \(1\) by Proposition 5. Therefore, \[M_{t+1}(\theta) \le \exp\bigl(4R(\theta)\bigr).\] ◻
Recall the definition of the \(\lfloor n/2\rfloor\)-hop potential which was introduced in [5], \[\phi_{\lfloor n/2\rfloor}(t) = \sum_{i=0}^{n-1} \bigl(X_i(t)-X_{i+{\lfloor n/2\rfloor}}(t)\bigr)^2.\] The lower-bound argument of Alistarh, Nadiradze, and Sabour shows that, for all sufficiently large \(t\), \[\mathbb{E}[\phi_{\lfloor n/2\rfloor}(t)]\ge c n^2.\] By rotational symmetry, the expected difference of each such pair is the same. Therefore, \[\mathbb{E}\bigl[(X_0(t)-X_{\lfloor n/2\rfloor}(t))^2\bigr] = \frac{1}{n}\mathbb{E}[\phi_{\lfloor n/2\rfloor}(t)] \ge cn.\] Theorem 4 gives \(\Pr(|X_0(t)-X_{\lfloor n/2\rfloor}(t)|\ge u) \le C\exp\left( -c\min\left\{\frac{u^2}{n},u\right\} \right).\) Thus, \[\mathbb{E}|X_0(t)-X_{\lfloor n/2\rfloor}(t)|^4 = 4\int_0^\infty u^3\Pr(|X_0(t)-X_{\lfloor n/2\rfloor}(t)|\ge u)\,du \le 4C\int_0^n u^3e^{-cu^2/n}\,du + 4C\int_n^\infty u^3e^{-cu}\,du \le C'n^2.\]
We now apply the Paley–Zygmund inequality [9] to the nonnegative random variable \((X_0(t)-X_{\lfloor n/2\rfloor}(t))^2\). Since \(\mathbb{E}[(X_0(t)-X_{\lfloor n/2\rfloor}(t))^2]\ge cn\) and \(\mathbb{E}[(X_0(t)-X_{\lfloor n/2\rfloor}(t))^4]\le C'n^2\), \[\Pr\left( (X_0(t)-X_{\lfloor n/2\rfloor}(t))^2\ge\frac{1}{2}\mathbb{E}[(X_0(t)-X_{\lfloor n/2\rfloor}(t))^2] \right) \ge \frac{1}{4} \frac{\mathbb{E}[(X_0(t)-X_{\lfloor n/2\rfloor}(t))^2]^2}{\mathbb{E}[(X_0(t)-X_{\lfloor n/2\rfloor}(t))^4]} \ge \frac{c^2}{4C'}.\] Hence \[\Pr\left( |X_0(t)-X_{\lfloor n/2\rfloor}(t)|\ge \sqrt \frac{cn}{2} \right) \ge \frac{c^2}{4C'}.\] Finally, \(\operatorname{Gap}(t)\ge |X_0(t)-X_{\lfloor n/2\rfloor}(t)|\), and therefore by Markov’s inequality \[\mathbb{E}[\operatorname{Gap}(t)] \ge C''\sqrt n.\] Thus, for sufficiently large \(t\) the expected gap is \(\Omega(\sqrt n)\). \(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\square\)