Skip to main content
3 of 3
Adds the missing case for $X^{(t)} = 0$.
Xi Wu
  • 143
  • 5

Concentration of a modified random walk

Let $\varepsilon$ be a number in $(0, 1)$, consider the following random walk on the real line $X^{(0)}, X^{(1)}, \dots$, where

  • $X^{(0)}=0$
  • If $X^{(t)} > 0$, then with probability $.5$, $X^{(t+1)} = X^{(t)} + (1-\varepsilon)$, and with probability $.5$, $X^{(t+1)} = X^{(t)} - (1+\varepsilon)$
  • If $X^{(t)} < 0$, then with probability $.5$, $X^{(t+1)} = X^{(t)} - (1-\varepsilon)$, and with probability $.5$, $X^{(t+1)} = X^{(t)} + (1+\varepsilon)$
  • If $X^{(t)} = 0$, then we do the same thing as the original random walk: with probability $.5$, $X^{(t+1)} = X^{(t)} + 1$, and with probability $.5$, $X^{(t+1)} = X^{(t)} - 1$.

In other words, if $X^{(t)}$ is biased from $0$, we want to "drag it towards $0$," and the strength is controlled by $\varepsilon$.

Is it the case that for nontrivial setting of $\varepsilon$ (for example, $\varepsilon = .3$), that $X^{(t)}$ is well concentrated around $0$ with smaller variance, compared to variance $t$ (thus a deviation of $\sqrt{t}$) in the case of $\varepsilon=0$?

Xi Wu
  • 143
  • 5