Let's say we have a 1D random walk starting at the origin where we go up $1$ with probability $1/5$, down $1$ with probability $1/5$, and stay put with probability $3/5$.

If we walk $n$ steps, what's the expected number of times we reach zero?

Here's a similar question, where instead they assume we move based on a continuous distribution.

I tried turning my discrete distribution into a continuous one using the pdf

$$f(x) = \frac{1}{5}\delta(x+1) + \frac{3}{5}\delta(x) + \frac{1}{5}\delta(x-1),$$

but the approach in that question didn't seem to work out.

Any ideas?

  • $\begingroup$ Do you count staying at zero as "reaching" zero, or are you interested in the expected number of returns to zero, counting each (possibly extended) stay at zero as one? $\endgroup$ – joriki May 23 '16 at 1:24
  • $\begingroup$ @joriki Yes, I'm counting staying at zero as "reaching" zero. $\endgroup$ – ZapMathigan May 23 '16 at 1:49

By linearity of expectation, the expected number of visits to the origin is the sum over the expected number of visits to the origin after $0\lt l\le n$ steps. That's the probability of taking $j$ up steps and $j$ down steps and staying put $l-2j$ times, summed for $0\le 2j\le l$, so the total is

$$ \sum_{l=1}^n\left(\frac35\right)^l\sum_{j=0}^{\left\lfloor\frac l2\right\rfloor}\binom l{j,j,l-2j}3^{-2j}\;. $$

I'm not aware that this can be simplified.

  • $\begingroup$ Thanks for this! Don't we also need to somehow incorporate the 1/5 probabilities into the formula? $\endgroup$ – ZapMathigan May 23 '16 at 2:53
  • $\begingroup$ @ZapMathigan: Yes, certainly, sorry, it should have been $5^{-n}$ instead of $5^{-l}$; fixed. $\endgroup$ – joriki May 23 '16 at 5:23
  • $\begingroup$ Actually I think your first answer was correct. Using your ideas, I had a double sum with summand Binomial[2 j, j] Binomial[l, 2 j] (1/5)^(2 j) (3/5)^(l - 2 j). That simplifies to your first answer. I did some simulations and it seems correct. $\endgroup$ – ZapMathigan May 23 '16 at 5:27
  • $\begingroup$ @ZapMathigan: Right, you had me confused for a moment there :-) You were right that we need to incorporate the $\frac15$ probabilities, but I'd already incorporated them. I reverted the edit. $\endgroup$ – joriki May 23 '16 at 6:56

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.