Watching a video about snakes and ladders (https://www.youtube.com/watch?v=k2ixp5VozIs) inspired me to dust off my markov-chain-memories and calculate the probability of winning the game after N rounds for normal and hardcore (ladders are snakes too) version.
Here’s my code: https://gist.github.com/SimonLammer/5f7c5fd4f9e60bba9fd13db0930ff83b
Normal: 61% after 55 rounds; 95% after 144 rounds; 99% after 233 rounds.
Hardcore: 4.5% after 55 rounds; 19% after 144 rounds; 32% after 233 rounds; 66% after 610 rounds; 95% after 1597 rounds; 99% after 2584 rounds.
I expected the hardcore version to be harder, but didn’t foresee a difference this big.
How could the number of expected snakes that were taken to win be calculated (aside from computer simulation)?
Off the top of my head, you would do it by getting the hitting probability of a snake from zero, and then the hitting probability of a snake from itself, and then take the expectation a la a geometric series.
And in case you don’t know how to calculate the hitting probability, there’s some notes on it here: http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf. More generally, Dexter’s notes (should come up if you Google it) are great for a number of topics in maths.
For an example of how you’d go about calculating it for your specific problem, consider the following: squares 1, 2, 3 and 4, a snake from 3 to 1, a dice that rolls 1 or 2, and finishing at 4. Then, letting hi be the probability of hitting 3 from square i,
h3 = 1
h4 = 0
h2 = 1/2h3 = 1/2
h1 = 1/2h3 1/2h2 = 3/4
More generally, for any Markov chain, for set A to be hit, the hitting probabilities are the minimal solution to
hi = 1, I in A
hi = Σj pij hj, for transition probabilities pij
Hopefully that makes sense, and feel free to DM about any stats questions, as it was the focus of my undergrad :)
Thank you.