Spencer Bliven

Thoughts and Research

The Statistics of Monopoly

February 22, 2012 | Posted in Math, Tagged , , , ,

American Edition Monopoly board. (Source: wikipedia)

When we were kids, my siblings and I each had our own favorite properties when playing monopoly. My brother always went for the hotel on Boardwalk. My favorite was St. Charles Place. It didn’t cost as much to develop, and I was convinced that people tended to land on St. Charles place a disproportionate amount of the time. I’d be delighted when I managed to purchase St. Charles, and every time someone landed on that square it would reinforce my conviction that St. Charles was the most profitable property in Monopoly.

Armed with a college-level understanding of statistics, I thought I would test my childhood hypothesis that the probability of landing on St. Charles is higher than for other properties. The movement aspect of Monopoly can be modeled as a Markov process, which just means that the probability of landing on a square depends only on what square you were on last term. Let \mathbf{x}_t be a row vector of length 40 giving the probability that a player will land on each square after t rolls. All players start on GO!, so

\mathbf{x}_t = \left[ 1, 0, 0, \dots, 0\right].

Dice Movement

Now define transition probabilities for moving from one square to another. Ignoring things like chance cards, Monopoly uses the sum of two dice to move, so the probability of moving from one square to another is a triangle distribution with a peak 7 squares forward. For instance, the probability of moving to each square if you were previously on GO! is

 \left[ 0, 0, \frac{1}{36}, \frac{2}{36}, \frac{3}{36}, \frac{4}{36}, \frac{5}{36}, \frac{6}{36}, \frac{5}{36}, \frac{4}{36}, \frac{3}{36}, \frac{2}{36}, \frac{1}{36}, 0, 0, \dots \right].

Here’s some matlab code to generate the full transition matrix. D[i][j] gives the probability of moving from square i to j after rolling the dice.

% Initialize transition matrix for dice movement
D = zeros(40);
D(1,3:13) = [1:6, 5:-1:1]/36;
for i = 2:40,
    D(i,:) = circshift(D(i-1,:),[0 1]);
end

We can calculate the probability of being on a particular square after t turns by repeatedly multiplying current state vector by the transition matrix.

 \mathbf{x}_t = \mathbf{x}_{t-1}D = \mathbf{x}_0 D^t

The probability of landing on each square during the first 50 turns. The board is oriented as above, with GO! in the lower right corner. Pure white indicates a probability of 1, while 50% gray corresponds to a probability of 0.025, which is average for a 40-square board.

Applying this for a few steps, it appears that all squares rapidly become equally probable. But would they eventually all have probability 1/40=.025? This can be checked by examining the eigenvectors of the transition matrix. The eigenvector corresponding to \lambda=1 gives the probabilities of landing on each square after an infinite number of rolls.

%% Find steady state
[V, l] = eigs(A',1,'lm');

xss = V'/sum(V); %x at steady state, eg t->infinity

Running this shows that all the squares do indeed have probability 1/40 at t=\infty. So if all movement were determined by dice roll, all spaces would be equally likely to be landed upon.

Jail and Chance cards

Now lets see what happens when all the detail of Monopoly are included in the model. There are a couple other ways players get moved around:

  • The dreaded Go to Jail space
  • Community Chest. Most of the 16 community chest cards deal with money, but one sends you to jail.
  • Chance. 10 of the 16 chance cards move the player around the board.

This type of movement can be modeled as a second transition matrix, which get applied after each dice roll. Most squares leave the player where they ended up. Landing on ‘Go to Jail’ has a 100% probability of sending you to the jail spot. Community chest has a 1/16 chance of sending you to jail, and a 15/16 chance of remaining on the same spot. The Chance squares are complicated, but we can work out the transition probabilities from Chance squares too.

% Probabilities for non-dice movement.
ND = eye(40);

% Go directly to jail
ND(31,:) = 0; % 'Go to Jail' is square 31
ND(31,11) = 1; $ 'Jail' is square 11

% Community Chest cards: 16 total
% Cards are assumed to be drawn uniformly at random with replacement.
% 15 Unchanged
chestSquares = [3, 34];
ND(chestSquares,:) = ND(chestSquares,:)*15/16;
% 1 Go directly to Jail
ND(chestSquares,11) = ND(chestSquares,11)+1/16;

% Chance card calculations-download code for details

% A turn consists of a dice roll and then some non-dice movement
A = D*ND;

By including non-dice movement, some squares become much more likely than others. For instance, it is impossible to end a turn on ‘Go to Jail’. Squares such as Railroads are more likely, since players who land on Chance could be sent there.

Probability of ending a turn on each space, including non-dice movement.

Steady state probabilities for each square using the full model. The red line shows the mean probability of 0.025, and a few notable squares are labelled.

RankSquareProbability
1Jail0.0570
2Illinois0.0317
3B&O Railroad0.0304
4New York0.0301
5Reading Railroad0.0301
6Water Works0.0294
7Communtity Chest0.0289
8Tennessee0.0286
9Free Parking0.0282
10Kentucky0.0278
11St. Charles0.0275

Conclusion

It turns out that St. Charles Place was not a particularly good space, since the probability of landing there is only 0.0275, slightly above average. I would have been much smarter to try to buy Illinois, which gets landed on significantly more often than average.

So what’s the optimum strategy for playing monopoly? Looking at steady state probabilities of landing on each square gives a hint to this, but doesn’t capture the full complexity of the game. It doesn’t factor in the costs and revenues for each property, nor can it provide advice on trading, selling, or improving properties. Finally, looking at steady state probabilities can be deceiving since the game starts far from steady state. For instance, Vermont Ave has a lower than average chance of being landed on. However, it is almost 50% more likely to be landed on 5 turns after starting from GO! than it would have been if the players began already spread out. Sometimes extra revenue early in the game can translate to a big advantage later on.

Now, who wants to play monopoly?

Code

Calculating the full transition matrix has a lot of cases, so I didn’t include the code here. If you’re curious, check out the full code from bitbucket. It was tested on both Matlab and the free alternative, Octave. The main script is called ‘MCMonopoly.m’.

All things lead to Philosophy

May 27, 2011 | Posted in Math, Tagged , , , ,

The following meme has been kicking around reddit and other sites recently:

Wikipedia trivia: if you take any article, click on the first link in the article text not in parentheses or italics, and then repeat, you will eventually end up at "Philosophy". –xkcd #903 alttext

Clearly this is not true for every single article (for instance, it is currently not true for "Philosophy" itself), but it is true for a surprising number of pages. There are hundreds of forum posts by people marveling over the length of the path from cheese to philosophy and drawing deep connections to the scourge of lactose intolerance. And of course, the popularity of the meme has lead to an extensive edit war between people trying to ‘fix’ pages such that they conform to the rule, and people trying to ‘break’ pages out of spite, and those just trying to revert all the changes done by the previous two groups. In my opinion, the fact that pages like “Philosophy” exist seems very unsurprising to me.

Wikipedia conjecture. Consider a directed graph where every node has outgoing degree exactly one. If nodes are added randomly in a scale-free manner (eg the probability of linking to an existing node is proportionate to that node’s incoming degree), then the expected fraction of nodes in the largest connected component will increase monotonically.
Philosophy corollary. Given a sufficiently large such graph, there will be a node which is reachable from a large fraction of the graph. Here “large” is defined as “large enough to stimulated discussion by bored reddit denizens.”

Perhaps I’ll try to prove this after quals, when I have more time for nonsense.

Probabilistic Towers of Hanoi

November 23, 2010 | Posted in Math, Tagged , , , ,
The Lunch of Hanoi

Yellow curry on rice, Thai iced tea, and mango sticky rice.

At lunch after stats class I received the three to-go boxes at right. Probably due to some sort of brain-addling by aforementioned stats class, this lead me to think about the Towers of Hanoi problem, and how in real life stacking problems (eg lunches, moving trucks, etc) it is often ok to have one or two big boxes stacked on top of little boxes. This led to the following problem:

Probabilistic Towers of Hanoi

Like the Towers of Hanoi problem, we have three pegs and a stack of N disks. Disks are initially sorted on one peg, and the goal is to move single disks between pegs until all the disks are stacked in order on the second peg.

Unlike Towers of Hanoi, we allow larger disks to be stacked on top of smaller disks. This exponentially reduces the number of moves required, since it effectively reduces the stack height by 1 (recall that solving Towers of Hanoi requires 2^n-1 moves).

However, every time we stack a larger disk on top of a smaller disk, the tower falls over with probability p. In general, p could be some function g(\cdot) which varies depending on the differences in disk sizes, the height of the stack, etc., or it could be something simple like a fixed number. If the tower falls we lose the game and civilization is destroyed. Alternately, maybe we just have to redo the fallen tower, wasting some moves to do so.

The probabilistic towers of hanoi problem then becomes: Given some probability \epsilon, what is the best strategy for moving disks such that the expected probability of failure is less than \epsilon and the expected number of moves is minimal?

Solution

If there is a fixed probability p of losing the game each time we add a disk to a stack that contains a smaller disk, we can make at most \left\lfloor \frac{log(1-\epsilon)}{log(1-p)}\right\rfloor inverted moves. These should be distributed in such a way as to reduce the number of moves as much as possible. For one inverted move, this is as follows:

  1. Disks 1…(n-2) from A to C (2^{n-2}-1 moves)
  2. Disk (n-1) from A to C (1 inverted move)
  3. Disk n from A to B (1 move)
  4. Disk (n-1) from C to B (1 move)
  5. Disks 1…(n-2) from C to B (2^{n-2}-1 moves)

This takes a total of 2^{n-1}-1 moves, including one inversion. That’s around 50% better than the original algorithm. If additional inverted moves are allowed while keeping the probability of failure low, they should be distributed evenly between steps 1 and 5 to further reduce the moves. Given sufficient inverted moves, this procedure will move a stack of n disks in only 3(2^{n/2}-1) moves.

Open Problems

The fixed-probability case isn’t particularly interesting statistically. A more interesting probability function would be some physics-inspired statistic reflecting how ‘top-heavy’ a pile is; a large disk perched precariously on top of a stack would be more likely to fall than a medium disk on a slightly smaller base. I feel like some surprising behavior could emerge in these situations requiring more clever algorithms.

For even n. For odd n, it takes
2^{(n+3)/2 }-3)
.

Latex!

November 22, 2010 | Posted in Math,Metablog, Tagged , , , ,

I installed a \LaTeX plugin! It will pretty up any of my mathy posts, and you can use it in comments too! For inline math formulas, surround your \LaTeX code with two dollar signs: $$\frac{4}{3}\pi r^3$$ gives \frac{4}{3}\pi r^3. For display equations, add an exclamation mark: $$!E\psi(r)=-\frac{\hbar^2}{2m}\nabla^2\psi(r)+V(r)$$ gives

E\psi(r)=-\frac{\hbar^2}{2m}\nabla^2\psi(r)+V(r)

If you need two dollar signs for some reason, use the html escape sequence for dollar, $.