Skip to main content
The last equation for E[Z] was supposed to have fractions but were not included by the author. I fixed this.
Source Link

From comments:

If you split the events into $4$ groups, say $A_n$ being at $(0,0)$ after $n$ steps without having hit the square, $B_n$ being at $(±1,0)$ or $(0,±1)$ after $n$ steps without hit the square, $C_n$ being at $(±1,±1)$ after $n$ steps without having hit the square, and $D_n$ first hitting the square at the $n$th step, then you get

  • $P(A_{n+1})=\frac14P(B_n)$
  • $P(B_{n+1})=P(A_n)+\frac12P(C_n)$
  • $P(C_{n+1})=\frac12P(B_n)$
  • $P(D_{n+1})=\frac14P(B_n)+\frac12P(C_n)$.

This will enable you to find $P(D_n)$ and so $∑nP(D_n)$ as the expected time to hit the square. You applied this and found the answer to be $4.5$, which is correct.

Alternatively, after one step you are at $(±1,0)$ or $(0,±1)$. Then you either

  1. hit the square on the next step or
  2. hit the square after two steps or
  3. are again at $(±1,0)$ or $(0,±1)$ after two steps.

This gives a easily solved expression for the expected number of steps to hit the square. If $Z$ is the number of steps needed to hit the square from any of the $(±1,0)$ or $(0,±1)$ points then you get $E[Z]=14×1+14×2+12×(2+E[Z])$$E[Z]=\frac14×1+\frac14×2+\frac12×(2+E[Z])$ implying $E[Z]=\frac72$; then add $1$ for the initial step from $(0,0)$ to get $\frac92=4.5$ again.

From comments:

If you split the events into $4$ groups, say $A_n$ being at $(0,0)$ after $n$ steps without having hit the square, $B_n$ being at $(±1,0)$ or $(0,±1)$ after $n$ steps without hit the square, $C_n$ being at $(±1,±1)$ after $n$ steps without having hit the square, and $D_n$ first hitting the square at the $n$th step, then you get

  • $P(A_{n+1})=\frac14P(B_n)$
  • $P(B_{n+1})=P(A_n)+\frac12P(C_n)$
  • $P(C_{n+1})=\frac12P(B_n)$
  • $P(D_{n+1})=\frac14P(B_n)+\frac12P(C_n)$.

This will enable you to find $P(D_n)$ and so $∑nP(D_n)$ as the expected time to hit the square. You applied this and found the answer to be $4.5$, which is correct.

Alternatively, after one step you are at $(±1,0)$ or $(0,±1)$. Then you either

  1. hit the square on the next step or
  2. hit the square after two steps or
  3. are again at $(±1,0)$ or $(0,±1)$ after two steps.

This gives a easily solved expression for the expected number of steps to hit the square. If $Z$ is the number of steps needed to hit the square from any of the $(±1,0)$ or $(0,±1)$ points then you get $E[Z]=14×1+14×2+12×(2+E[Z])$ implying $E[Z]=\frac72$; then add $1$ for the initial step from $(0,0)$ to get $\frac92=4.5$ again.

From comments:

If you split the events into $4$ groups, say $A_n$ being at $(0,0)$ after $n$ steps without having hit the square, $B_n$ being at $(±1,0)$ or $(0,±1)$ after $n$ steps without hit the square, $C_n$ being at $(±1,±1)$ after $n$ steps without having hit the square, and $D_n$ first hitting the square at the $n$th step, then you get

  • $P(A_{n+1})=\frac14P(B_n)$
  • $P(B_{n+1})=P(A_n)+\frac12P(C_n)$
  • $P(C_{n+1})=\frac12P(B_n)$
  • $P(D_{n+1})=\frac14P(B_n)+\frac12P(C_n)$.

This will enable you to find $P(D_n)$ and so $∑nP(D_n)$ as the expected time to hit the square. You applied this and found the answer to be $4.5$, which is correct.

Alternatively, after one step you are at $(±1,0)$ or $(0,±1)$. Then you either

  1. hit the square on the next step or
  2. hit the square after two steps or
  3. are again at $(±1,0)$ or $(0,±1)$ after two steps.

This gives a easily solved expression for the expected number of steps to hit the square. If $Z$ is the number of steps needed to hit the square from any of the $(±1,0)$ or $(0,±1)$ points then you get $E[Z]=\frac14×1+\frac14×2+\frac12×(2+E[Z])$ implying $E[Z]=\frac72$; then add $1$ for the initial step from $(0,0)$ to get $\frac92=4.5$ again.

Source Link
Henry
  • 159.3k
  • 9
  • 128
  • 264

From comments:

If you split the events into $4$ groups, say $A_n$ being at $(0,0)$ after $n$ steps without having hit the square, $B_n$ being at $(±1,0)$ or $(0,±1)$ after $n$ steps without hit the square, $C_n$ being at $(±1,±1)$ after $n$ steps without having hit the square, and $D_n$ first hitting the square at the $n$th step, then you get

  • $P(A_{n+1})=\frac14P(B_n)$
  • $P(B_{n+1})=P(A_n)+\frac12P(C_n)$
  • $P(C_{n+1})=\frac12P(B_n)$
  • $P(D_{n+1})=\frac14P(B_n)+\frac12P(C_n)$.

This will enable you to find $P(D_n)$ and so $∑nP(D_n)$ as the expected time to hit the square. You applied this and found the answer to be $4.5$, which is correct.

Alternatively, after one step you are at $(±1,0)$ or $(0,±1)$. Then you either

  1. hit the square on the next step or
  2. hit the square after two steps or
  3. are again at $(±1,0)$ or $(0,±1)$ after two steps.

This gives a easily solved expression for the expected number of steps to hit the square. If $Z$ is the number of steps needed to hit the square from any of the $(±1,0)$ or $(0,±1)$ points then you get $E[Z]=14×1+14×2+12×(2+E[Z])$ implying $E[Z]=\frac72$; then add $1$ for the initial step from $(0,0)$ to get $\frac92=4.5$ again.