Prerequisites
Let’s denote the cities as A, B, V, and H and establish what we know already.
- We know that the second journey ends in H.
- On this basis, it is impossible for the third journey to end in H, since we are travelling from H.
- We have 4 cities in total, and from each city, we could travel to each of the other 3.
- On this basis, for each journey point, there is a \frac{1}{3} chance of travelling to each other city. For instance, if we are at A, then we can either travel to B, H or V.
- The probability of being in any of those cities after the third journey is \frac{1}{3}.
Finding the probability distribution of H across multiple journeys.
The journey will follow the prototype V-H-X-X-X-X-X-X-H.
X here simply denotes an unknown city, although it’s important to note that each X must be different to the X preceding it. Also note how there are 8 dashes representing 8 journeys, so we actually have a total of 9 cities in our path.
At first glance it seems like we could just distribute the probability over \frac{1}{3} for each movement. But this wouldn’t work since we have the first and second steps predetermined.
In order to work out the probability of being in H after each movement, we need to take the probability of not being in H from the previous movement, and then distribute this over 3 branches.
Since the last known point is city H, we should try and work out the probability of being in city H after each move.
- We are predetermined to be in H after the first movement, as shown in the prototype.
- This means that the probability of being in H after the second movement is 0, since we are departing city H.
- From this point onwards the exact movement pattern is indeterminate. After the third move, we have a \frac{1}{3} chance of being in H.
- After the fourth move is where it starts to get a little more involved. We will need to get the probability that we were not in H beforehand (since we can’t travel from H to H) and then apply 3 possible branches to this probability. The probability of not being in H before the move is \frac{2}{3}, and we have a \frac{1}{3} chance of moving anywhere else except this city. This gives us a \frac{2}{3} \times \frac{1}{3} = \frac{2}{9} chance of being in H.
- The step we did above now needs to be repeated, until we reach the end of the chain.
Each time we are essentially performing the following steps:
- calculate the probability of not being in H.
- divide this by 3 to account for the branching distribution.
Algebraic Formation of Distribution
We can write this algebraically.
If X_n is the probability of being in H after n journeys, then
Xn+1=1.0−Xn3X_{n+1} = \frac{1.0 - X_n}{3}Xn+1=31.0−Xn
We are making 8 journeys, so we will calculate the value of X_8.
|
|
| X_1 |
1 |
| X_2 |
0 |
| X_3 |
\frac{1 - 0}{3} = \frac{1}{3} |
| X_4 |
\frac{1 - \frac{1}{3}}{3} = \frac{2}{9} |
| X_5 |
\frac{1 - \frac{2}{9}}{3} = \frac{7}{27} |
| X_6 |
\frac{1 - \frac{7}{27}}{3} = \frac{20}{81} |
| X_7 |
\frac{1 - \frac{20}{81}}{3} = \frac{61}{243} |
| X_8 |
\frac{1 - \frac{61}{243}}{3} = \frac{182}{729} |
By following the distribution appropriately, we can see that there are 182 possibilities out of 729 where we will end up in city H. Therefore, probability p = \frac{182}{729}.
The Second Probability
Keep in mind that the probability of each city being chosen per-turn is equally distributed. What isn’t equally distributed is the probability of a single city at a single point overall, since our starting data of V and H is predetermined.
Now we can use this to work out probability q.
If X_8 is \frac{182}{729}, then the probability of being in any of the other three cities is 1 - \frac{182}{729} which is \frac{547}{729}.
Final Steps
We can now distribute this across three choices, giving us \frac{547}{729} / 3 which is \frac{547}{2187}. Therefore probability q = \frac{547}{2187}.
Our final step for this question is to add these together to find probability p + q.
p + q = \frac{182}{729} + \frac{547}{2187} = \boxed{\frac{1093}{2187}}
Our final answer is therefore \boxed{\frac{1093}{2187}}.