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

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.

• This would be more intuitive to me with $M_n=1$ iff $|X_n|\ge |Y_n|$ — would that equally difficult case also get what you want? – Matt F. Dec 27 '19 at 8:50
• An $O(\sqrt{N})$ bound seems clear since you can look at the 2-dimensional random walks obtained by specifying two directions in advance and then only keeping the steps along those. – Christian Remling Dec 27 '19 at 17:06
• For biased r/w, I guess the question is whether more than one component of the drift vector takes the maximal value. If not, say the $n$th component takes the maximal value. Now each time $X_i=X_n$, there is a probability $p_i$ that this never occurs again. So the total number of switches is bounded above by a sum of $d-1$ geometric random variables, so that for all $N$, the expected number of switches up to time $N$ is bounded above as required. – Anthony Quas Dec 27 '19 at 22:26
• The question of how the number of switches scales with $d$ is interesting... – Anthony Quas Dec 27 '19 at 22:27

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.