1 problem found
A point moves in unit steps on the \(x\)-axis starting from the origin. At each step the point is equally likely to move in the positive or negative direction. The probability that after \(s\) steps it is at one of the points \(x=2,x=3,x=4\) or \(x=5\) is \(\mathrm{P}(s).\) Show that \(\mathrm{P}(5)=\frac{3}{16},\) \(\mathrm{P}(6)=\frac{21}{64}\) and \[ \mathrm{P}(2k)=\binom{2k+1}{k-1}\left(\frac{1}{2}\right)^{2k} \] where \(k\) is a positive integer. Find a similar expression for \(\mathrm{P}(2k+1).\) Determine the values of \(s\) for which \(\mathrm{P}(s)\) has its greatest value.
Solution: After \(5\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 1 \text { - go positive every time}\\ 4 & 0 \\ 3 & \binom{5}{1} \text { - go positive every time but 1} \\ 2 &0 \\ \hline & 6 \end{array} Therefore there are \(\frac{6}{2^5} = \frac{3}{16}\) ways to get to \(\{2,3,4,5\}\) After \(6\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 0 \\ 4 & \binom{6}{1} \text { - go positive every time but 1}\\ 3 & 0 \\ 2 & \binom{6}{2} - \text{ - go positive every time but 2} \\ \hline & 21 \end{array} Therefore there are \(\frac{21}{2^6} = \frac{21}{64}\) ways to get to \(\{2,3,4,5\}\) After \(2k\) steps we can reach \(2\) or \(4\). To get to \(2\) we must take \(k+1\) positive steps and \(k-1\) negative steps, ie \(\binom{2k}{k-1}\). To get to \(4\) we must take \(k+2\) positive steps and \(k-2\) negative steps, ie \(\binom{2k}{k-2}\) Therefore there are \(\binom{2k+1}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k}} \binom{2k+1}{k-1}\) After \(2k+1\) steps we can reach \(3\) or \(5\). To get to \(3\) we must take \(k+2\) positive steps and \(k-1\) negative steps, ie \(\binom{2k+1}{k-1}\). To get to \(5\) we must take \(k+3\) positive steps and \(k-2\) negative steps, ie \(\binom{2k+1}{k-2}\) Therefore there are \(\binom{2k+2}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k+1}} \binom{2k+2}{k-1}\) To find the maximum of \(P(s)\) notice that \begin{align*} && \frac{P(2k+1)}{P(2k)} &= \frac12 \frac{\binom{2k+2}{k-1}}{\binom{2k+1}{k-1}} \\ &&&= \frac12 \frac{(2k+2)!(k-1)!(k+2)!}{(2k+1)!(k-1)!(k+3)!} \\ &&&= \frac12 \frac{2k+2}{k+3} = \frac{k+1}{k+3} < 1 \end{align*} So we should only look at the even terms. \begin{align*} && \frac{P(2k+2)}{P(2k)} &= \frac14 \frac{\binom{2k+3}{k}}{\binom{2k+1}{k-1}} \\ &&&= \frac14 \frac{(2k+3)!(k-1)!(k+2)!}{(2k+1)!k!(k+3)!} \\ &&&= \frac14 \frac{(2k+3)(2k+2)}{k(k+3)} \\ &&&= \frac{(2k+3)(k+1)}{2k(k+3)} \geq 1 \\ \Leftrightarrow && (2k+3)(k+1) &\geq 2k(k+3) \\ \Leftrightarrow && 2k^2+5k+3 &\geq 2k^2+6k \\ \Leftrightarrow && 3 &\geq k \\ \end{align*} Therefore the maximum is when \(s = 2\cdot 3\) or \(s = 2\cdot 4\) which we computed earlier to be \(\frac{21}{64}\)