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. 
 A: 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.
