A particles moves in $\mathbb{R^2}$ started at the origin. At each stage $i (i = 1, 2, …)$, the particles would move, independently of all the stages before, one of the four directions North, East, South and West 1 unit, with probability $1 \over 4 $ each.Let $T_n$ be the distance from the origin just after $n$ steps. What is $E(T_n)$. I tried define 4 $1\times 2$matrice with only $1,0,-1$ in all entries. The use technique similar to simple random walk in 1 dimension and we know that for a $1\times 2$ matrice $(x,y)$, the distance from origin =$\sqrt {x^2+y^2}$ but i am not sure how to like the 1 D to 2 D. As in 2 D there are 4 possible direction.
[Math] Random walk in the plane
probabilityprobability theory
Related Solutions
Thanks for the interesting and creative problem.
It made me curious as to how large the path could get for Energy = 20, so I mapped it:
The origin is the green cell and the possible end cells are yellow. The cells that your question asks for percentages on are the orange squares.
With problems like these with a gajillion possibilities, I lean heavily toward using a simulator.
I ran 4 simulations, each for 100 million trials, and since all 4 of them gave similar results, I concluded that the number of trials for each run was large enough. Here are the results:
------------------------ Original answer end ------------------------
Edit: This may be overkill, but I was curious how many distinct stopping points there were, and I wanted to see how the probabilities decreased as the endpoint got further from the origin.
So, I altered the sim again and re-ran it for 2,147,483,646 runs, and here are those results. The percentages are out of all possible paths, not just for the white slice shown. I am showing only the slice because it considers all 161 distinct points (and makes it small enough to read, but you'll probably need to save it to your machine to view it). All other possible ending points are a reflection of these points.
Quite a few possible ending points far from the origin were never hit once, and some were hit only once (15,10; 16,7; and 17,0)
Let $(S_0,T_0)=0$ and define $\{(S_n,T_n):n=0,1,2,\ldots\}$ by the transition probabilities $$ \mathbb P((S_{n+1},T_{n+1}) = (i',j') \mid (S_n,T_n) = (i,j) = \begin{cases} \frac14,& |i'-i| + |j'-j| = 1\\ 0,& \text{otherwise}. \end{cases} $$ By symmetry, $$ \mathbb P((S_1,T_1) = (1,0)) = \mathbb P((S_1,T_1) = (0,1)) = \mathbb P((S_1,T_1) = (-1,0)) = \mathbb P((S_1,T_1) = (0,-1)) = \frac14. $$ For the distribution of $(S_2,T_2)$, there are three cases. First, the case where two steps are made in the same direction: $$ \mathbb P((S_2,T_2) = (2,0)) = \mathbb P((S_2,T_2) = (0,2)) = \mathbb P((S_2,T_2) = (-2,0)) = \mathbb P((S_2,T_2) = (0,-2)). $$ These probabilities are given by \begin{align} \mathbb P((S_2,T_2) = (2,0)) &= \mathbb P((S_2,T_2) = (2,0)\mid (S_1,T_1)=(1,0))\mathbb P((S_1,T_1)=(1,0))\\ &= \left(\frac14\right)^2\\ &= \frac1{16}. \end{align} Second, the case where one horizontal step is made and one vertical step is made: $$ \mathbb P((S_2,T_2) = (1,1)) = P((S_2,T_2) = (-1,1)) = P((S_2,T_2) = (1,-1)) = P((S_2,T_2) = (-1,-1)). $$ Since the steps could have been made in two different orders, these probabilities are $2\cdot\frac1{16}=\frac18$.
Third, the case where $(S_2,T_2)=(0,0)$. There are four ways this can happen, so the probability is $4\cdot\frac1{16}=\frac14$.
The distribution of $(S_3,T_3)$ may be found by a similar analysis - the probabilities will be multiples of $\frac1{4^3}=\frac1{64}$ depending on how many paths there are that end at a given point.
Best Answer
An explanation is given here.
Using that formula you get for the 2D case for the distance from the origin just after n steps:
$$\sqrt{2n} \dfrac{\Gamma(\frac{3}{2})}{\Gamma(\frac{1}{2})}=\sqrt{\frac{n}{2}}$$