Chutes and Ladders, the real deal

    Now that the project is nearing an end, I thought it would be a good time to branch out from the Chutes and Ladders world and start looking in-depth at possible applications for the results I've obtained. Markov Chains are used all over the place to model real-world processes, but finding situations which are analagous to moving along a Chutes and Ladders board is a bit more tricky, especially because chutes and ladders make the movement a lot more irregular.

    One useful first step is to remove all of the "fluff" in the game and break it down to its simplest mathematical form. For processes that are Markov Chains, this can be done by representing them as "directed graphs". A graph, in this context, refers to a series of points connected by a series of edges. You can draw two points on a piece of paper, connect them with a line, and bam, you have a graph. Straightforward, right? Perhaps you can already see why graphs are so useful for simplifying complicated processes. In a directed graph, each of these points corresponds with a state in a Markov Chain, and an edge connecting two points signifies that there is a non-zero probability of going between the corresponding states. However, since the probability of going to state B from state A isn't necessarily the same as the probability of going to state A from state B, it is also necessary to specify which state is the "start" state and which state is the "end" state, and this is conventionally done by placing an arrow on the edge that points in the direction of the end state. Thus, there may be two edges between two vertices A and B: one that starts on A and ends on B and one that starts on B and ends on A.

    Here's an example of a directed graph for the "simplified" game of Chutes and Ladders introduced a few months ago:

    The simplified game (the arrow represents a chute)

     

    A rather crude directed graph. Putting in arrows made the image too cluttered, so here a green line signifies that it starts on the square furthest to the left between the two, a yellow line signifies that it starts and ends on the same square, and a red line signifies that it starts on the square furthest to the right between the two.

    Note that here the square on which the top of the chute is located is not represented by a vertex in the directed graph. It is what we might call a "pseudo-state" rather than a real state, since it is never possible for a player to be located on that state at the end of his or her turn. This square instead influences the graph by increasing the probability that a player lands on the square on which the end of the chute is located.
   
    More juicy details to come in the next post. Stay tuned.