A probability problem in the plane Suppose 2 particles are placed at the origin of the real line.Every second they move one unit right or left with probability $0.5$ independent of the other particle and previous moves.I know how to compute the probability that they both be at the same place after $N$ seconds.I want to compute an analogue probability in the plane.This time 2 particles are placed at the origin of the real plane and every second they move one unit up or right or down or left with probability $0.25$ independent of the other particle and previous moves.I want to compute the probability that they both be at the same place after $N$ seconds.
I don't know how to compute it.Any hint would be appreciated.
 A: This is a classical problem in stochastic processes: Exact Probability of Collision of Two Independent Random Walkers After N Steps. The 1-D version of the problem can be found here. Let's first do a quick recap on the 1-D problem by presenting two (equivalent) ideas:
Idea 1. After $N$ seconds, there are $2^N$ possible paths for a given particle on the 1-D line (left or right move at each second). In order to have the two particles meet on the 1-D line after $N$ seconds, the number of right moves (and thus the left moves) must be the same for both of the particles, i.e. they can both have 0 right moves, 1 right moves, ... , or $N$ right moves (out of $N$ moves). Given that the two particles move independently, each with equal probability of moving left or right at each second, we have that the probability of the two particles meet on the 1-D line after $N$ seconds is given by
$$\frac{\sum_{k = 0}^N {N \choose k}^2}{\left(2^N\right)^2} = \frac{\sum_{k = 0}^N {N \choose k}^2}{2^{2N}}.$$
Idea 2. For each particle, we consider its path after $N$ seconds as a realization of the random walk. For example, suppose $N = 5$, one possible realizations of the two particles can be given by
\begin{align*}
L_1 \rightarrow R_1 \rightarrow R_1 \rightarrow L_1 \rightarrow R_1\\
\\
R_2 \rightarrow R_2 \rightarrow L_2 \rightarrow L_2 \rightarrow R_2
\end{align*}
Now for every possible realization pair of the two particles, we perform the following operation: 1) reverse and flip each move of the second particle; 2) attached the reversed and flipped path of the second particle to the path of the first particle, i.e. for the above example we have
\begin{align*}
L_1 \rightarrow R_1 \rightarrow R_1 \rightarrow L_1 \rightarrow &R_1\\
&\downarrow\\
L_2 \leftarrow L_2 \leftarrow R_2 \leftarrow R_2 \leftarrow &L_2\\
\\
\Longleftrightarrow \quad L_1 \rightarrow R_1 \rightarrow R_1 \rightarrow L_1 \rightarrow R_1 \rightarrow L_2 \rightarrow &R_2 \rightarrow R_2 \rightarrow L_2 \rightarrow L_2
\end{align*}
Thus, whenever the two particles meet after $N$ seconds (like the example above), it can be equivalently interpreted as a (single) particle ends at the origin after $2N$ seconds. To achieve this, note that there are $2N \choose N$ possible ways to have a particle move right. As such, the corresponding probability is given by
$$\frac{{2N \choose N}}{\left(2^{2N}\right)}.$$
Comparing the results from the two ideas above, the denominators are the same, while the numerator gives a combinatorial identity:
$$\sum_{k=0}^N {N \choose k}^2 = {2N \choose N}.$$
Now we consider the generalized problem from the 1-D line to a 2-D plane. At each second, the two possible directions (left or right) are replaced by four (left, right, up, or down). However, using exactly the same as Idea 2 above, we conclude that whenever the two particles meet after $N$ seconds, it can be equivalently interpreted as a (single) particle ends at the origin after $2N$ seconds. After $2N$ seconds, there are $4^{2N}$ possible paths for a given particle on the 2-D plane. The total possible ways of a particle ends at the origin after $2N$ second is given by
\begin{align*}
&\underbrace{{2N \choose N}}_{\text{select } N \text{ seconds for right and up moves}} \times \sum_{k = 0}^N \underbrace{{N \choose k}}_{\text{select } k \text{ seconds for right moves}} \times \underbrace{{N \choose k}}_{\text{select } k \text{seconds for left moves}}\\
&= {2N \choose N} \times \sum_{k = 0}^N {N \choose k}^2 = {2N \choose N} \times {2N \choose N} = {2N \choose N}^2
\end{align*}
according to the combinatorial identity above.
To sum up, the probability of the two particles meet on the 2-D plane after $N$ seconds is given by
$$\frac{{2N \choose N}^2}{4^{2N}}.$$
