# (2-D Random Walk) Probability of Returning to Origin

I know this is a long question, but please bear with it since it is just because I go into a lot of detail:

A particle moves 1 step in the N, E, S, or W direction each with probability 1/4 every second. What's the probability the particle ever returns to the origin?

The hint: First calculate the expected number of total visits to the origin. What is the connection between that number and the probability of ever returning?

To calculate the expected number of total visits to the origin, I used linearity of expectation. P(X_n) corresponds to the probability that on the nth move, the particle will return to the origin. I got:

i Odd: P(X_n) = 0, since it can never return to the origin in an odd number of moves.

i Even: P(X_n) = SUM from j=0 to n{[P(N)P(S)]^(j)C(2j, j)[P(E)*P(W)]^(n-j)*C(2n - 2j, n - j)}.

• [P(N)*P(S)]^(j) is j steps each in the NS direction, since since the number of N and S steps must be equal and the number of E and W must be equal also to return to the origin
• C(2j, j) is the number of ways it can move in the NS direction when 2j are in that direction
• [P(E)*P(W)]^(n-j) is n-j steps each in the EW direction or the steps not taken in the NS direction
• C(2n - 2j, n - j) is is the number of ways it can move in the EW direction when 2n - 2j are in that direction. EDIT: I figured out what was missing. A factor of C(2n, 2j) to account for which 2j of the 2n steps are in the NS direction and which 2n-2j are in the EW direction.

The sum is supposed to count over the ways it can return to the origin in n steps, with 2j of them being in the NS direction and 2n-2j of them in the EW direction.

The sum simplified to P(X_n) = SUM from j=0 to n{(1/16)^(n)*C(2i, i)*C(2n - 2j, n - j)*C(2n, 2j).

I thought that the expected number of total visits to the origin is then just the sum over all terms, with the odd terms being zero. Setting x = n/2 to sum over all even terms gave me +inf.

I am now stuck on, as suggested in the hint, how to relate this, the expected number of total visits to the origin, to the probability of ever returning to the origin. The correct answer is 1, and I believe it is a logic question. I would like to know:

1. Is my calculation of the expected number of total visits to the origin correct? EDIT: I figured out what was wrong with my calculation and fixed it.

1. How is the the expected number of total visits to the origin related to the probability of ever returning to the origin? This probability is 1, but I don't know why. If the expected value of returns to the origin is infinite, why does that mean it will always return to the origin?

• Suppose $p$ is the probability of not returning to the origin, given we start there. Let $X$ be the number of times we return to the origin (given we start there). Then $P[X=0]=p$, $P[X=1] = (1-p)p$, $P[X=2]=(1-p)^2p$ and so on. So you can compute $E[X]$ and observe what happens when $p>0$ versus $p=0$. – Michael Oct 8 '18 at 2:22