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}}$.
Best Answer
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.