New answers tagged


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

Top 50 recent answers are included