Random walks: How many times does the largest component change?

Question

My understanding is that for an unbiased random walk (starting at the origin) on $\mathbb R$ with $N$ steps that the expected number of sign changes is $O(\sqrt N)$. For a biased walk I believe the expected number is $O(1)$. In either case it is $O(\sqrt N)$.

Now suppose we have a random walk $(X_n,Y_n)$ on $\mathbb R^2$ and are interested in the number of times the largest component changes. Formally define $M(n) = 1$ if $X_n \ge Y_n$ and $M(n) = 2$ if $X_n < Y_n$. We want to bound $\mathbb E|\{n \le N: M(n) \ne M(n+1)\}|$.

To get a bound we only need to consider the random walk $X_n-Y_n$ on $\mathbb R$. By the previous result the sign changes $O(\sqrt N)$ times on expectation. But sign changes correspond to the largest component changing and we're done.

For dimensions $d>2$ this trick no longer works. In that case is anything known about the expected number of times the largest component changes? Are there any known order bounds depending on $d$ and $N$? I suspect $O(\log(d) \sqrt N)$ bounds might be possible.

I am trying to find answers online but I can't seem to even find a reference for the $O(1)$ result I mentioned.

Answer 1

For a large class of unbiased random walks, the expected number of switches is of order $\Theta (\sqrt{N \log d})$.

It is closely related to the growth of regret in online learning, see, e.g., [1]; it is fine if the increments are biased as long as all components have the same mean. The exact answer depends on the step distribution of the random walk. For concreteness, suppose $X_n=(X_n(i) : 1 \le i \le d)$ is a random walk in $\mathbb R^d$ with $d$ independent components, and each component has $\pm 1$ increments of the same mean $\mu \in (-1,1)$. Denote $M_n:= \max_{j\le d} X_n(j)$. Let $J_n$ denote the index of a maximal component at time $n$. (Precisely, let $J_0=1$. Given an integer $n \ge 1$, suppose that $J_{n-1}$ has already been defined. If $X_{n}(J_{n-1})=M_n$ then take $J_n:=J_{n-1}$; otherwise, set $J_n$ to be the minimal $j$ such that $X_{n}(j)=M_{n}$.) Finally, let $S_n:=\sum_{k=1}^n {\mathbf 1}_{J_k \ne J_{k-1}}$ be the number of times the maximal component switches by time $n$. Observe that for $n \ge 1$, $$ M_{n+1}-M_n =X_{n+1}(J_n)-X_n(J_n)+ 2 \cdot{\mathbf 1}_{J_{n+1} \ne J_n} \, . $$ Therefore $M_n-n\mu-2S_n$ is a martingale for $n \ge 0$, so for all $N>0$, $${\mathbb E} M_N-N\mu- 2 {\mathbb E}S_N=0 \,. \quad (*)$$

The multivariate central limit theorem, and the standard asymptotics for the maximum of $d$ Gaussians (see, e.g., Solution 18.7, page 348 in [2]), imply that as $N \to \infty$, $${\mathbb E}\Bigl[\frac{M_N-N\mu}{\sigma\sqrt{N}}\Bigr] \to \sqrt{2\log d} \, , $$ where $\sigma^2=1-\mu^2$ is the variance of the increments. By (*), as $N \to \infty$, $${\mathbb E}\Bigl[\frac{S_N}{\sigma\sqrt{N}}\Bigr] \to \sqrt{(\log d)/2} \, . $$

The analysis above can be extended to the case where each independent component has increments of the same mean $\mu$ and variance bounded above and below by positive constants. (In that case $M_n-n\mu-cS_n$ will be a super- or sub-martingale depending on the value of $c>0$.) If the increments of different components have different means, then one can restrict attention just to those components where the increments have a maximal mean.

[1] Towards Optimal Algorithms for Prediction with Expert Advice. Nick Gravin, Yuval Peres, and Balasubramanian Sivan. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, 528-547

[2] Karlin, Anna R., and Yuval Peres. Game theory, alive. Vol. 101. American Mathematical Soc., 2017.