Multiple layers of probability


I'm sorry for not using the correct terms, but I have a problem that involves multiple layers of probability that I could solve by myself eventually, but it would take days of manual labour to systematically work through, so there must be a faster way. I would very much appreciate any advice on how to create an equation to address this puzzle.

Imagine a game where a letter is posted to a random address. The recipient of that letter will then forward it to a new address, and so on and so. The letter begins its journey by being sent to an address in London.
The probability that a letter received in London will be sent to a new address in London is 50%, that it will be forwarded to an address elsewhere in the UK is 30%, sent to an address abroad is 16% and lost for good in the postal system 4%.
The probability that a letter received elsewhere in the UK will be sent to an address in London is 10%, sent to an address elsewhere in the UK is 80%, sent abroad 7% and lost for good 3%.
The probability that a letter received abroad will be sent to an address in London is 2%, elsewhere in the UK 1%, to an address abroad 92% and lost for good 5%.

I would need to calculate the probabilities that, after 26 trips, the letter:

1. Will have disappeared
2. Will have disappeared specifically from an address in London
3. Will have disappeared specifically from an address abroad

I could easily calculate specific probabilities, i.e. the probability that it would move to London to abroad, then elsewhere in the UK, then back to London, then abroad, etc; but the complexities of this puzzle escape me. Likewise, I could manually figure this out if there were only three or four trips involved, but 26 is too many. If someone could please provide a hint on how to get moving with this then I would be extremely grateful.

Thank you in advance :)


Ambassador to the humans
What you have is a Markov chain. You have all the necessary info to define your transition matrix. Finding the probability of starting at position London and ending at position X is what the row corresponding to London will tell you after taking the matrix to the 26th power. Luckily this is fairly easy to do in software. I'll leave the details up to you for now but hopefully they gives you a good starting point.
Hi @Dason
Thank you very much! This brought me a massive step closer. I've been reading about Markov chains and definitely see how the application, but my biggest issue is the 'lost' option in my example that has no arrows out. From what I can see, this may mean it's a hidden Markov chain, but this doesn't seem to be an exact fit. I've mapped the chain to demonstrate I am trying to figure this out myself! Could you confirm for me whether a regular Markov chain would solve this or whether its some variant (such as the HMC)?
So grateful for the help! Screen Shot 2021-09-22 at 16.07.28.png


Ambassador to the humans
A regular Markov chain would work just fine and your situation is a common case. Basically you just add a case for "lost" and that case has a probability of 1 of transitioning into "lost" so essentially once it's there it's stuck.
Dear @Dason ,

Thanks again for the reply. I've found a really useful excel solver but I think I must be misinterpreting the output somehow as the 'checker' for my puzzle says the figures are not correct. I'm happy with the input but would you mind helping me (hopefully a final time!) check my understanding of the output?

For Q1: I believe it's just .67705 (the output in cell D26)
As Q2 and Q3 have the same logic, I only need to check Q2. Here, I'm assuming that this is the chance that the letter ended in London on round 25 (.02675 - from cell A25) multiplied by the probability that the letter goes missing from a London address (.4, as in the original text). My answer here then is .02675 * .4 = .0107.

Am I reading the numbers incorrectly somehow? Any advice appreciated as always!

Picture 1.jpg
Last edited: