this post was submitted on 10 Jul 2023
6 points (100.0% liked)

math

804 readers
5 users here now

General community for all things mathematics on @lemmy.world

Submit link and text posts about anything at all related to mathematics.

Questions about mathematical topics are allowed, but NO HOMEWORK HELP. Communities for general math and homework help should be firmly delineated just as they were on reddit.

founded 1 year ago
MODERATORS
mrh@lemmy.world
6
Snakes and Ladders (lemmy.sdf.org)
submitted 1 year ago by GitProphet@lemmy.sdf.org to c/math@lemmy.world
4 comments fedilink hide all child comments
 

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)?

you are viewing a single comment's thread
view the rest of the comments
[–] chumbalumber@lemmy.blahaj.zone 2 points 1 year ago (1 children)

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 points 1 year ago* (last edited 1 year ago) (1 children)

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 :)