6
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – user44143
    Dec 27, 2019 at 8:50
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 27, 2019 at 17:06
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 27, 2019 at 22:26
  • $\begingroup$ The question of how the number of switches scales with $d$ is interesting... $\endgroup$ Dec 27, 2019 at 22:27

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.