The probability of ending up at a corner of a 3×3 square after 4 moves starting at the center

combinatoricsprobability

In my programming class, we've been practicing trying to calculate the worst-case scenario. Recently, I was assigned a problem as homework that was interesting, but I wasn't able to find a solution to it. The problem goes a little like this:

Suppose your robot is playing a game on a 3×3 board of unit squares. The robot starts at the center square, and has four options. It can either move to the square above, to the left, to the right, or below. Because your robot has not been optimized yet, it will move randomly to either of the 4 options. The robot will have the option to move up to 4 times, but will stop if it ever reaches a corner square. what is the probability that the robot will end up at a corner square after the end of the 4 moves? Additionally, if a robot ever moves off the edge of the board, it will be warped to the opposite square. For example, if it were at the leftmost square that was in the middle row and chose to move to the left for the next move, it would be warped to the rightmost square in the middle row.

I'm still pretty new to probability and all of this, but I'm guessing the first step is to find the total amount of sequences, and then finding the sequences that end up on a corner square. I was able to calculate the first 3 scenarios fine. The minimum moves needed to reach a corner square is at least 3 moves. I've found $4^4$ possibilities for the 4 moves. For the 2 moves and 3 moves, I've figured out there's 8 possibilities of getting to the corner for each. Is this correct? After this, I've got pretty stumped, as I'm not sure how to calculate the number of times it can get to the corner squares with $4$ moves.

EDIT: Ok so I've done a bit more work. For doing 2 moves, there are only 8 possibilities. The robot has to move out of the center, and then to one of the corner squares around it. For doing 3 moves, there were also 8 possibilities. The robot has to move out of the center, then moves the same direction again to warp to the opposite side, and then can go to one of the 2 corners. And for 4 moves, it turns out there's no way to utilize the warp to go to a corner. So the only way is either going to a side square, back to center, and then repeating the scenario with 2 squares. There's 4 ways to do the first part and 8 for the second part, so another 32. This adds up to 48 ways. However, I'm still having difficulty calculating the entire total. Does anyone have any ideas on how to get the amount of any possible moves?

Best Answer

A direct count of possibilities isn’t too hard if you organize it properly. There are $4^4=256$ possible four-move sequences. I’ll use $L,R,U$, and $D$ to denote moves to the left, right, up, and down, respectively.

  • Any sequence that starts $LU,LD,RU,RD,UL,UR,DL$, or $DR$ reaches a corner. The robot actually stops at that point, but each of these two-move sequences can be extended to a four-move sequence in $4^4=16$ ways, so these $8$ paths account for $8\cdot16=128$ of the $256$ four-move sequences: we just ignore the last two moves.
  • Any sequence that starts $LLU,LLD,RRU,RRD,UUL,UUR,DDL$, or $DDR$ also reaches a corner; each of these $8$ sequences can be extended to a four-move sequence in $4$ ways, so they account for another $8\cdot4=32$ four-move sequences altogether.
  • Any sequence that starts $LR,RL,UD$, or $DU$ returns to the centre, and we’ve already seen that there are $8$ two-move sequences from the centre that reach a corner; that accounts for another $4\cdot8=32$ four-move sequences that reach a corner. There are altogether $4\cdot4=16$ possible two-move sequences, so the other $8$ of them do not reach a corner from centre; this accounts for $4\cdot8=32$ four-move sequences that do not reach a corner.
  • Any sequence that starts $LLR,RRL,UUD$, or $DDU$ reaches an edge square, as if just one move had been made, and has $2$ one-move continuations that reach a corner; that accounts for another $4\cdot2=8$ four-move sequences that reach a corner. From an edge square there are also $2$ moves that do not reach a corner, so this category accounts for $4\cdot2=8$ four-move sequences that do not reach a corner.

The first and third categories above cover all sequences that change direction on the second move, and the second and fourth categories account for all sequences that first change direction on the third move. If the first three moves are the same, i.e., $RRR,LLL,UUU$, or $DDD$, the robot is back at the centre and cannot reach a corner. From that point $4$ moves are possible, so this final category covers $4\cdot4=16$ four-move sequences, none of which reaches a corner.

We’ve now accounted for

$$128+32+32+32+8+8+16=256$$

four-move sequences, which is all of them, and found that $200$ of them reach a corner. The probability that the robot reaches a corner within four moves is therefore

$$\frac{200}{256}=\frac{25}{32}\,.$$

And we have the information to say more: the first category above shows that the probability that the robot reaches a corner in two moves, for instance, is

$$\frac{128}{256}=\frac12\,.$$

Similarly, the second category shows that the probability that the robot reaches a corner in three moves is

$$\frac{32}{256}=\frac18\,.$$

And of course this means that the probability that it takes the robot all four moves to reach a corner is

$$\frac{25}{32}-\frac12-\frac18=\frac5{32}\,.$$

Related Question