A Random walk Problem

Question

Consider a particle that moves left/right along a straight line. The particle's initial position is 0. It moves left or right with equal probability, and the step size is 1. Each time the particle move to the right side, we record the position as $P_{right}$, so $P_{right}$ is a random variable. Similarly, we also record position $P_{left}$ Example:

• t0: particle at 0,
• t1: particle moves right to 1, record $P_{right}$ position 1
• t2: particle moves left to 0, record $P_{left}$ position 0
• t3: particle moves left to -1, record $P_{left}$ position -1
• t4: particle moves right to 0, record $P_{right}$ position 0
• t5: particle moves right to 1, record $P_{right}$ position 1

Question: How to calculate the mean value of $P_{right} - P_{left}$, or $\mathbf{E}(P_{right} - P_{left})$.

I have done some numerical experimental, it seems the mean value should be 1. But I don't know how to prove it.

import numpy as np

// Answer suggested by Lorenzo Najt
def calc0():
  r = np.random.choice([1, -1], 1000000)
  p = r.cumsum();

  right = []
  left = []
  for c, pos in zip(r, p):
    if c > 0:
      right.append(pos)
      if left:
        left.append(left[-1])
    else:
      left.append(pos)
      if right:
        right.append(right[-1])
  return np.mean(right) - np.mean(left)


# My original numerical simulation
def calc1():
  r = np.random.choice([1, -1], 1000000)
  p = r.cumsum();

  right = []
  left = []
  for c, pos in zip(r, p):
    if c > 0:
      right.append(pos)
    else:
      left.append(pos)

  return np.mean(right) - np.mean(left)


print(calc0())
print(calc1())

Answer 1

The initial conditions seem a little fuzzy, though I don't think they matter in the end. It makes more sense to consider this as a process.

Let $P^L_t, P^R_t$ be the left and right values at time $t$, and $D_t = P^R_t - P^L_t$. Call the particle $x$.

Suppose that $P_t^{L}$ has just been changed for the first time in $ > 1$ steps -- that is, we just stepped left after stepping right (possibly for a long streak). Then $P^R_t = P^L_t + 1$, so $D_t = P_t^R- P_t^L = 1$.

By translation invariance of $D$, we may as well assume that $P_t^R = 1, P_t^L = 0$ and $x = 0$.

Now there are two possibilities:

• Suppose we step right. Now $P_t^L = 0, P_t^R = 1, D_t = 1$ and the point $x$ is at $1$. We are going to step right $k$ more time, possibly $k = 0$, and each time $D_t$ increases by $1$. At the $k$th step right, $D_t = 1 + k$ (including $k = 0$). If we step left at some point, $D_t$ becomes $1$.
• Suppose we step left $k$ times, $k > 0$. Then, $D_t$ increases by $1$ each time ($P^L$ decreases by $1$ and $P^R$ stays the same), and on the first step right, $D$ resets to $1$.

This convinced me that overall the process $D_t$ looks like the following Markov chain on $\{1,2,3, \ldots, \}$, with transition probabilities $P(n,n+1) = 1/2$ and $P(n,1) = 1/2$ for all $n$.

The stationary distribution of this chain is $\pi(i) = 2^{-i}$. (I just checked this directly.)

Thus, the expected value against the stationary distribution is $\sum_{i = 1}^{\infty} i 2^{-i} = 2$. By the Ergodic theorem for Markov chains (example 6.24 in Durret ), the long term average value of $D_t$ will be $2$.

I see you got 1 via numerical calculation, so perhaps I made a mistake here...