3
$\begingroup$

It is well known that for a discrete random walk on the integers with a fair coin, the expected distance of the walker from the origin after $N$ time steps is $\sqrt{\frac{2N}{\pi}}$ if $N$ is large. For example, Wolfram Mathworld has a thorough explanation here.

Consider instead the following situation. We have two types of weighted coins. Type A coins have a probability $1/3$ to land heads, and a probability $2/3$ to land tails. Type B coins have a probability $2/3$ to land heads, and a probability $1/3$ to land tails. At each integer location, we place one of the coin types there at random, so that each integer location has exactly a 50% chance to get a type A coin, and a 50% chance to get a type B coin (coins are independently chosen at each integer location).

When the walker is at a particular integer location, she flips the coin placed there and goes one step right if it lands heads, and one step left if it lands tails. I believe in the literature this is known as a "Random Walk in a Random Environment" (RWRE)

What then is the expected value of the distance of the walker from the origin after $N$ steps for large $N$? I have done numerics that suggest that this value is still $\sim \sqrt N$, but the constant term is probably not $\sqrt{\frac{2}{\pi}}$.

Improve this question
$\endgroup$
3
$\begingroup$

The main result of the paper "The Limiting Behavior of a One-Dimensional Random Walk in a Random Medium" by Y. B. Sinai is that the distance of the walker from the origin at time $n$ is of order $(\log n)^2$. He analysed a bigger class of transition probabilities but pointed out your case an example.

Moreover, the constant term in front of $(\log n)^2$ is random with respect to the placement of the coins but concentrates conditionally on it. I do not know if anybody has worked out an explicit formula for its expectation. This seems to go in contrast with your numerics, so check that it actually applies to your case and I did not understand your question poorly.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks! I suspect that I did not do my numerics carefully enough. $\endgroup$ – Darren Ong Feb 12 '19 at 0:37
  • $\begingroup$ Sinai's result is that, for all "good" coin placements (that is, except for the "bad" placements constituting a set of small probability), conditionally on the placement, the random distance of the walker from the origin is $O(\ln^2 n)$ in probability. However, this by itself does not preclude the possibility that the expected distance is $\ge c\sqrt n$ for some $c>0$ and all $n$ -- even conditionally, for each of the"good" placements; let alone unconditionally; cf. the Fatou lemma. So, the OP's simulations (?) may be right. $\endgroup$ – Iosif Pinelis Feb 12 '19 at 12:43
  • $\begingroup$ Previous comment continued: Another possibility is that the asymptotics $O(\ln^2 n)$ is not detectable here even for $n$ as large as $10^8$, say -- which could be another explanation for the OP's results. $\endgroup$ – Iosif Pinelis Feb 12 '19 at 12:43
  • $\begingroup$ On this, you are right, $\sqrt n /(\log n)^2$ is around $5$ for $n=10^6$, so it might still be interpreted as a different constant. For the OP: were the numerics simulations or numerical approximations of the probabilities? $\endgroup$ – LopiJ Feb 12 '19 at 12:54
  • $\begingroup$ @LopiJ : The detectability is actually of lesser concern to me than the "Fatou" comment. The main point is that the convergence in probability by itself is not enough to get the asymptotics for the expected distance. $\endgroup$ – Iosif Pinelis Feb 12 '19 at 13:01
1
$\begingroup$

To add to LopiJ's answer: there is a rich literature on RWRE. For a generalization of this model (corresponding to long range jumps being allowed), see the work of Bolthausen and Goldsheid https://arxiv.org/abs/0710.5854, which clarifies when you should expect a $\sqrt{N}$ scaling (and CLT) and when Sinai scaling. In a nutshell, you get a CLT only if the local drift is $0$ for each coin, like for simple random walk.

Improve this answer
$\endgroup$
  • $\begingroup$ Please see my comments to LopiJ's answer. What do you think? $\endgroup$ – Iosif Pinelis Feb 12 '19 at 12:45
  • $\begingroup$ @iosif pinelis see above $\endgroup$ – ofer zeitouni Feb 12 '19 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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