# The probability of stepping and ending where you start.

A particle moves $N$ steps as detailed here: in every steps it is to turn north, south, east or west, one unit at a time, with unchanging probability and with no dependence on any recent step.(That creates a uniform sample space, $|\Omega|=4^N$). What is the probability that it ends in its starting point?

I know I have to find an event A, and combinatorially compute $|A|$. My biggest problem is: for every single step I make north I walk one south(respectively) and do the same with east and west? Because if so, I think I can solve it on my own. This kind of question is confusing me, though. I could really use your observation.

• Yes: you return to the start if and only if the number of steps north equals the number south and the number east equals the number west. – Brian M. Scott Mar 17 '15 at 7:19

Let the probabilities be $p_N,p_S,p_E\text{ & }p_W$ for North, South, East and West. Let $n$ be the number of steps. This is a multinomial distribution, and the probability is:
$$P(O)=\begin{cases} \sum_{i=0}^\frac{n}{2}\frac{n!}{i!^2(n-i)!^2}p_N^ip_S^ip_E^{n-i}p_W^{n-i}&n\text{ even}\\ 0&n\text{ odd}\\ \end{cases}$$