# Tag Info

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