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)?
4 Comments
chumbalumber@lemmy.blahaj.zone · 2 pts · 3y
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.
chumbalumber@lemmy.blahaj.zone · 2 pts · 3y
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 :)
GitProphet@lemmy.sdf.org · 1 pts · 3y
Thank you.