Starting at $(0, 0)$, Richard takes $2n+1$ steps, with each step being one unit either East, North, West, or South. For each step, the direction is chosen uniformly at random from the four possibilities. Determine the probability that Richard ends at $(1, 0)$.
Problem
Source: Canada Repêchage 2016/7
Tags: combinatorics, counting, probability
lucasxia01
19.06.2016 04:54
Let's define the number of steps in the north direction as $N$, south as $S$, east as $E$, and west as $W$. We know that $N = S$ and $E = W + 1$. Also, the total number of steps is $E + W + N + S = 2n + 1$. We can substitute in for two of the variables to get $2W + 1 + 2N = 2n + 1 \implies W + N = n$. We can use the balls and urns method to obtain the total amount of ways of reaching the desired destination: $\binom{n+1}{1} = n+1$. Now, we must order the steps. We have $W$ steps west, $W+1$ steps east, and $n-W$ steps north and south. Therefore the total ways to order a path with $W$ moves in the west direction is $\frac{(2n+1)!}{W!(W+1)!((n-W)!)^2}$. We now find that the total ways that fit the condition is $\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2} = \frac{4^{2n+1} \cdot ((n + \frac{1}{2})!)^2}{\pi((n+1)!)^2}$ (By WolframAlpha). The total amount of paths is $4^{2n+1}$ so the probability is $\frac{\frac{4^{2n+1} \cdot ((n + \frac{1}{2})!)^2}{\pi((n+1)!)^2}}{4^{2n+1}} = \boxed{\frac{\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2}}{4^{2n+1}}=\frac{((n + \frac{1}{2})!)^2}{\pi((n+1)!)^2}}$.
Edit: My earlier method didn't consider ordering the path so it was wrong. However, I don't know how to evaluate this summation.
Edit2: I have used WolframAlpha to find the summation!
Edit3: I put both answers just in case
DIffCALCFTW
19.06.2016 04:57
One must realize that in order for Richard to reach the coordinate point $(1,0)$, that the number of steps he takes to go north will be the same as the number of steps that he takes to go south and $1$ more than what he takes to go east and west. Therefore let's denote the variable $n$ which are the number of steps he takes to go any of the directions. Therefore the probability to go north or south is $\binom{2n+1}{n}$. Since the total amount of paths are he must take is $4^{2n+1}$ , the probability of ending at his chosen point of $(1,0)$ is $\frac{\binom{2n+1}{n}^2}{4^{2n+1}}$
mathematiculperson
19.06.2016 05:06
lucasxia01 wrote:
Let's define the number of steps in the north direction as $N$, south as $S$, east as $E$, and west as $W$. We know that $N = S$ and $E = W + 1$. Also, the total number of steps is $E + W + N + S = 2n + 1$. We can substitute in for two of the variables to get $2W + 1 + 2N = 2n + 1 \implies W + N = n$. We can use the balls and urns method to obtain the total amount of ways of reaching the desired destination: $\binom{n+1}{1} = n+1$. The total amount of paths is $4^{2n+1}$ so the probability is $\boxed{\frac{n+1}{4^{2n+1}}}$.
Don'you have to think about how many there are turning ways for each $N$,$S$,$E$,$W$?
lucasxia01
19.06.2016 05:10
yes, I have fixed my solution but there doesn't seem to be a plausible way that I know of evaluating that summation.
mathematiculperson
19.06.2016 05:17
lucasxia01 wrote: yes, I have fixed my solution but there doesn't seem to be a plausible way that I know of evaluating that summation. You're final answer should be $\boxed{\frac{\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2}}{4^{2n+1}}}$, I think.
lucasxia01
19.06.2016 05:24
I fixed it with WolframAlpha but I don't know how else to solve this problem...
mathematiculperson
19.06.2016 05:29
lucasxia01 wrote: I fixed it with WolframAlpha but I don't know how else to solve this problem... You have already solved the problem,$\boxed{\frac{\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2}}{4^{2n+1}}}$should't be changed anymore, I think...
lucasxia01
19.06.2016 05:33
Are the answers of this contest (it is a contest I presume?) in any form?
mathematiculperson
19.06.2016 05:39
lucasxia01 wrote: Are the answers of this contest (it is a contest I presume?) in any form? I want to know too
shinichiman
19.06.2016 05:54
lucasxia01 wrote:
We now find that the total ways that fit the condition is $\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2} = \frac{4^{2n+1} \cdot ((n + \frac{1}{2})!)^2}{\pi((n+1)!)^2}$ (By WolframAlpha).
A way to compute this sum. We have $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}.$$Note that by Vandermonde's identity we have $$\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}= \binom{2n+1}{n}.$$Therefore, $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}^2.$$Thus, the answer is $\frac{\binom{2n+1}{n}^2}{4^{2n+1}}$, which is the same as DIffCALCFTW's answer.
mathematiculperson
19.06.2016 06:11
shinichiman wrote: lucasxia01 wrote:
We now find that the total ways that fit the condition is $\sum_{W=0}^{n} \frac{(2n+1)!}{W!(W+1)!((n-W)!)^2} = \frac{4^{2n+1} \cdot ((n + \frac{1}{2})!)^2}{\pi((n+1)!)^2}$ (By WolframAlpha).
A way to compute this sum. We have $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}.$$Note that by Vandermonde's identity we have $$\sum_{k=0}^n \binom{n}{n-k} \binom{n+1}{k}= \binom{2n+1}{n}.$$Therefore, $$\sum_{k=0}^n \frac{(2n+1)!}{(n-k)!(n-k+1)!(k!)^2}= \binom{2n+1}{n}^2.$$Thus, the answer is $\frac{\binom{2n+1}{n}^2}{4^{2n+1}}$, which is the same as DIffCALCFTW's answer. Yes! You are right! Thinking arranging $2n+1$ cards,which consists of $4$ kinds(Let $A$,$B$,$C$,$D$). You have to put $n$ cards of either $A$ or$B$,and same as to $C$or$D$. But you have to put $A$ one more than other three cards. So, the number of arrangements is $({}_{2n+1}C_{n})^{2}$
DIffCALCFTW
19.06.2016 08:19
Yes, you guys are correct. Thank you @shinichiman for elaborating on using Vandermonde's identity.