Recently, I've been trying to derive the probability of a random walker in 2D returning to the origin in N steps, but for some reason, I get the wrong result. Below is my derivation:
The probability of a random walker returning to origin in 1D is:
$P_N = {N\choose N/2}\frac{1}{2^N} = \frac{N!}{(\frac{N}{2}!)^2\cdot2^N}$
For a 2 dimensional case then, the probability should be just the product of probabilities in the x and the y direction:
$P_N = P_{n_x}\cdot P_{n_y} \ni: N = n_x + n_y \wedge n_i = 2k_i \mid k_i \in \mathbb{N}_0$
The above statement holds for a given set of $n_x$ and $n_y$, so to account for all possible combinations, I expressed $n_y = N-n_x$ and summed over all $n_x$:
$P_N = \sum_{n_x=0}^N P_{n_x}\cdot P_{N-n_y} = \sum_{n_x=0}^N {n_x\choose{n_x/2}}\frac{1}{2^{n_x}} \cdot {N-n_x\choose{(N-n_x)/2}}\frac{1}{2^{N-n_x}} = \sum_{n_x=0}^N {n_x\choose{n_x/2}}{N-n_x\choose{(N-n_x)/2}}\frac{1}{2^{N}} $
Finally noting, that the number of steps has to be even, I expressed $N=2K, n_x = 2k$ and summed over k instead:
$P_N = \sum_{k=0}^K {2k\choose{2k/2}}{2K-2k\choose{(2K-2k)/2}}\frac{1}{2^{2K}} = \frac{1}{2^{N}}\sum_{k=0}^K {2k\choose{k}}{2(K-k)\choose{K-k}} = \frac{1}{2^{N}}\sum_{k=0}^K \frac{(2k)!(2[K-k])!}{(k!)^2((K-k)!)^2} $
which is wrong. The right answer is given by:
$P_N = \frac{1}{4^{N}}\sum_{k=0}^K \frac{(2k)!}{(k!)^2((K-k)!)^2}$
Could someone explain to me, where in my reasoning I am wrong? Thank you for your help!
The correct expression is $$ P_N = \sum_{k=0}^K\binom{2k}k2^{-2k}\binom{2K-2k}{K-k}2^{-2(K-k)}\color{red}{\binom{2K}{2k}2^{-N}} $$
The idea is that $$ P_N=\sum_{k=0}^KP(\text{return to }(0,0)\mid n_X=2k)P(n_X=2k) $$ You had already incorporated $P(\text{return to 0}|n_X=2k)$, but had forgotten $P(n_X=2k)$. Note that $n_X$ is a binomial random variable; each of the $2K$ steps are independently either horizontal or vertical with probability $1/2$. Therefore, $P(n_X=2k)=\binom{2K}{2k}2^{-N}$.
Perhaps of interest is this summation-free formula for the probability: $$ P_N=4^{-N}\binom{N}{N/2}^2 $$ To see this, suppose the $i^{th}$ step of the random walk is to $(x_i,y_i)$, and consider the change of coordinates $$ s_i=x_i+y_i\\ t_i = x_i-y_i $$ Now the $s_i$ and $t_i$ are independent $1$D random walks. The original random walk returns to the origin if and only if both $s_i$ and $t_i$ do. Since they are independent, we just multiply the probabilities of each returning.