What Shall We Do with a Drunken Sailor?
An Introduction to Markov Chains
📚 Connect with us. Want to hear what’s new at The Pragmatic Bookshelf? Sign up for our newsletter. You’ll be the first to know about author speaking engagements, books in beta, new books in print, and promo codes that give you discounts of up to 40 percent. Note: Pythonic Programming by Dmitry Zinoviev was just released this week!
The problem of Drunken Sailor must be as old as professional mariners — or at least as old as mathematics. Many flavors of the problem exist, so let’s stick to this one:
A drunken sailor returns from a tavern to his ship. The distance between the tavern and the ship is N steps. With each intermediate step, the sailor has chance f of stepping forward, chance b of stepping backward, and chance of 1-f-b of standing still. Where does the sailor end up at the end of the day?
We can translate the problem into the language of states and transitions. For the sake of example, let’s assume that N=4. The system of the sailor, the tavern, and the path between the two can be in one of the N+1=5 states S[i]: (1) the sailor is in the tavern; (2) the sailor is 1 step away from the tavern; (3) the sailor is halfway from the tavern; (4) the sailor is 1 step away from the ship; and (5) the sailor is on the ship. The probability of being…
