The Most Popular Square in Infinite Monopoly

Monopoly is a classic board game made by Parker Brothers. Each player starts with a certain amount of money. The players take turns rolling dice to move their piece around a list of properties. If the player has enough money to purchase the property they land on then they have the option of buying the property. If someone else has the property already then the player has to pay rent instead. If the player cannot afford rent then they will angrily flip over the board, ending the game. This concludes a typical game of Monopoly. In the end, there is no winner, only broken friendships.

Clearly, Monopoly is a gentleman's game and so everyone should learn some basic strategy. This blog post will outline which properties are the most important to control and give an estimate of how much money you can expect to bring in from each property. To do this we will calculate which squares on the board are the most popular in Monopoly. To do this we will make a few assumptions:

1. Monopoly is a very very long game that never ends (this is pretty much true).
2. A player will always buy out of jail as soon as they can. This isn't true of course. It might be a better idea to wait until your opponents are about to cross your biggest properties before you buy out of jail and risk paying huge rent fees yourself.

Okay, so how can it be done?

That's a good question. I want to answer this by giving a general outline of what I kept in mind while solving this problem. The details are left out in all but the creative step of the problem. If you'd like to fill in the details yourself you'll need to be familiar with Markov Chains.
Here is the outline I made while I solved this problem:

I. Analyze the Problem.

This step consists of making observations that might help move the problem into abstraction. My observations for this problem were:

1. I am interested in finding the probability of being somewhere on a board at a specific time.
2. I know that Markov Chains can be used to find the probability of something happening at a particular time.
3. To be a Markov chain requires the object in question to have no memory between each random move, however Monopoly does not satisfy this property.
4. Monopoly does have a memory, rolling doubles three times will send you to jail.

I will stop the analysis here. We have come to a problem in our analysis, but instead of giving up, we will force our approach to work. This is the creative part of problem solving.

II. Form a strategy

The problem has already taken some form in our minds from analyzing it. Now we will make our strategy explicit.

1. Modify the game of Monopoly into a new game, Markovopoly (get it?).
2. Solve for the distribution in the new game.
3. Use the solution of Markovopoly to get the solution for the original Game.

III. Carry out the strategy

Modifying the game of Monopoly into a new game is what I would consider the creative step in solving the problem. There are an infinite number of possible ways to "modify Monopoly", how should we choose to modify it? Well, we have to check out the strategy. We intend for whatever modification we make to 1. be solved by Markov Chains, and 2. Give enough information to be able to solve the original problem. This type of thought is no different from how a poet might choose his words when he has a particular emotion he wants to express. We choose things from the vast number possibilities with a goal in mind, and that is where there is creativity. How to come up with this part of the solution is part luck and part logical. Somehow we want to modify the game as little as possible so that we can keep goal 2. in mind, but we also want to modify it enough so that it will meet goal 1. If you'd like to try to come up with the solution now I suggest not scrolling down any more.
Here is the modified game, Markovopoly:

The way the new game works is this: It's just like normal Monopoly, except if you roll doubles you move out a layer. If you move past the third layer you go to jail. If you roll something besides doubles then you go back to the inner most layer. This version of Monopoly IS a Markov Chain. Now we can solve for the probability of landing on each square in Markovopoly, and then add each squares probability, along with it's two clones, to get the solution for the original game.

Now, instead of showing you how to analyze the game I just built, which is quite messy and took a computer, I will show how to solve this type of problem in general. A Markov Chain is a set of states and the probability of transitioning from one state to another state after a state change. For example, flipping a coin multiple times is a Markov Chain. The two states are heads and tails. The probability of going from state 1 (heads) to state 2 (tails) is 50% each flip. In fact each transition has a probability of 50%. We can store this information in a matrix like so:

.		Heads	Tails
	Heads	50%	50%
	Tails	50%	50%

Of course this example isn't terribly interesting, since we already fully understand what's going to happen at any time in the Markov Chain. So to further the point let's come up with a new example. This one can be about weather forecasting, and no it's not necessarily meant to be realistic. Here we will say there are 2 types of days, sunny days and rainy days. If it is a sunny day today, then tomorrow it will be a sunny day with 90% probability. This means 10% of days after sunny days must be rainy. Now if it is a rainy day, and since rainy days tend to all clump together, the next day has a probability of 40% to rain.

We can organize this data again in a matrix.

		Sunny	Rainy
	Sunny	90%	10%
.	Rainy	60%	40%

Now, someone might ask, "if today it is rainy, then what is the probability that it will be rainy in 2 days?" We can analyze our system and see there are 2 possible things that can happen tomorrow if it's rainy today. We can have sun tomorrow, and rain in 2 days, or we can have rain tomorrow, and rain in 2 days as well. The probability of the first event happening is $60\%\times10\%=6\%$, and the second has a probability of $40\%\times40\%=16\%$. Adding these together, tells us the probability of it raining in 2 days, given it is raining today, is $22\%$. Now, if we calculate the square of the matrix we gave for our Markov chain we will notice something:

		Sunny	Rainy
	Sunny	87%	13%
.	Rainy	78%	22%

This table actually shows the transition probability if the state change was over 2 days instead of just 1 day! In general we can find the probability that any day is rainy by calculating the limit of this matrix's powers as it goes to infinity. This is how we can solve the Markovopoly game as well, though we'd need a computer.

IV. Looking Back

This is the most important part of solving a problem. There was some level of ingenuity required to solve this problem, so it is worth looking back on and trying to save that ingenuity. We introduced a modified version of the game to solve, and it overcame an obstacle. How we chose the modified game has some structure. It somehow gives our Markov Chain "memory" by introducing states. We now have a general principle we can apply in future problems: If a system has a memory, but is very close to a memory-less system that can be analyzed, then we can introduce new states to serve in place of the memory. In our problem the new states were the outer layers of the Monopoly board.

The results

Here is a table giving the percent of the time each square is landed on:

	Square Name	Probability
	Jail	5.33%
	Community Chest	2.82%
	Tennessee Avenue	2.77%
	New York Avenue	2.74%
	Free Parking	2.72%
	St. James Place	2.71%
	Atlantic Avenue	2.71%
	Ventnor Avenue	2.71%
	B&O Railroad	2.70%
	Water Works	2.70%
	Kentucky Avenue	2.69%
	Marvin Gardens	2.69%
	Illinois Avenue	2.68%
	Pacific Avenue	2.68%
	Chance	2.67%
	Indiana Avenue	2.64%
	Pennsylvania Railroad	2.62%
	North Carolina Avenue	2.61%
	Community Chest	2.53%
	Virginia Avenue	2.53%
	Pennsylvania Avenue	2.46%
	States Avenue	2.44%
	Short Line	2.38%
	Electric Company	2.36%
	Baltic Avenue	2.33%
	Community Chest	2.31%
	Income Tax	2.30%
	Mediterranean Avenue	2.29%
	Chance	2.29%
	St. Charles Place	2.28%
	Go	2.28%
	Connecticut Avenue	2.28%
	Reading Railroad	2.27%
	Vermont Avenue	2.27%
	Oriental Avenue	2.27%
	Chance	2.27%
	Boardwalk	2.26%
	Luxury Tax	2.23%
	Park Place	2.19%
	Go To Jail	0.00%

The expected value of each square for each turn you own it (assuming none are Monopolies):

	Property	Value
	Boardwalk	$1.13
	Park Place	$0.77
	Pacific Avenue	$0.70
	Pennsylvania Avenue	$0.69
	North Carolina Avenue	$0.68
	Marvin Gardens	$0.65
	Atlantic Avenue	$0.60
	Ventnor Avenue	$0.60
	Illinois Avenue	$0.54
	Kentucky Avenue	$0.48
	Indiana Avenue	$0.48
	New York Avenue	$0.44
	Tennessee Avenue	$0.39
	St. James Place	$0.38
	Virginia Avenue	$0.30
	States Avenue	$0.24
	St. Charles Place	$0.23
	Connecticut Avenue	$0.18
	Vermont Avenue	$0.14
	Oriental Avenue	$0.14
	Baltic Avenue	$0.09
	Mediterranean Avenue	$0.05

The value of each Monopoly (in Dollars per turn):

	Monopoly	Value of Monopoly Per Turn
	Purple	$16.23
	Light Blue	$38.65
	Pink	$58.18
	Orange	$79.55
	Red	$85.5
	Yellow	$94.51
	Green	$101.76
	Blue	$77.94

Conclusion

The most valuable Monopoly to own is actually the green one. However, you probably have a better shot at getting the blue one since it is only 2 properties. The data above can be used to formulate a general strategy and to plan your trades exactly. You only want to make trades which have a positive expected value, (and you should consider the expected COST of landing on your opponent's new properties as well).

Now, about the more general problem at hand. I think it is worth mentioning that this exact type of analysis is what Google uses to sort the pages in search history. Pages are rated highly depending on the probability of you randomly clicking links and ending up there. This is a Markov process and it gives a natural ranking by computing the limiting distribution.

Hope you enjoyed!

Water and Wine

Some time ago I heard an interesting riddle that gave out quite a few headaches. I've been told this puzzle originated from The Republic by Plato, though I don't know if that's the real source of this riddle. His congratulations go out to whoever can solve this puzzle by thought experiment alone.

Here is the riddle:
1. Get 1 cup of wine and 1 cup of water.
2. Take a table spoon of wine and put it into the water.
3. Mix thoroughly.
4. Take a table spoon of the now water and wine mixture and put it back into the wine.

Now the question: at the end of the procedure which cup has a higher ratio of foreign substance to original substance? Is the water cup more polluted by wine or the wine cup more polluted by the water?

Most people's first reaction would be to say the water cup has surely been more polluted. We put a table spoon of pure wine into the water, but we only put a mixture of water and wine back into the wine glass. This is the most obvious observation of course, and there is a subtle observation that might lean you towards the other direction.

Even though we put a table spoon of pure wine into a the glass of water, and we put the mixture into the glass of wine. The effect of the wine glass being less than full means whatever we put into it should contaminate it more than if the glass had been full.

The last paragraph gives the argument for why it may be either side which is more polluted, or maybe an argument why they might be the same. I suggest to take your side now, as the rest of the post will describe the solution.

There are lots of ways to solve this puzzle, I will give the way I find the most elegant. It is similar to a type of argument that's used in mathematics called a combinatorial argument. We measure the same thing in two different ways and then since both measurements are of the same thing the measurements must be the same. This argument has the advantage in this situation of not worrying about the sequence of events outlined in the procedure. If we were to simply work out the amount of wine and water in each cup at each stage then we would come to a mess of fractions.

In order to use the strategy it's necessary to name the different pieces of fluid. The following image shows how I chose to label the water and wine in each glass. Now consider ways we can make a full glass of fluid. If we look at what's in the water glass it must measure up to 1 cup. This is because we took 1 table spoon of fluid out and put back 1 table spoon. Therefore $$A + B = 1 cup$$. On the other hand we started with 1 cup of water, so if we add up all the water we should get 1 cup. This means $$A + D = 1 cup.$$ These two equations cannot both be true unless $B = D$. So we can conclude both cups are equally polluted.

I hope you all enjoyed this one :).

Making Change

Since this is the first blog post on here I decided we could tackle a classic problem.  Given some collection of coins (say pennies, nickels, dimes, quarters, etc.) how many ways can the coins be combined to make some given amount of change?  More explicitly, given a set of distinct positive integers  $\{x_1, x_2, ... ,x_n\}$ and a value $V$, how many ways are there to make $V$ cents using coins valued $x_1, x_2, ... , x_n$?

This problem is given on Project Euler here.  In this post I'm going to show how to solve the Project Euler problem (using C#)..

From the link above:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

$$1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) \text{ and } £2 (200p)$$

How many different ways can £2 be made using any number of coins?

Running a brute force algorithm on this would take forever, so instead we can try to devise a clever algorithm.  First it might be helpful to imagine the problem if we didn't have so many coins.  It's quite a pain to keep track of how many different coins there are when we try to think of a way to solve this problem.  Instead we will solve a smaller problem by hand: how many ways are there to make 200p using only 1p and 2p coins?

This is a much easier problem.  We can easily divide this into cases.  There is as few as $0$ 2p pieces and as many as $100$.  In any configuration if we knew how many 2p pieces there were then we would automatically know how many 1p pieces there were since the total value of the coins is 200p.  Therefore, there are 101 ways to make 200p out of 1p and 2p pieces.

The 2 coin case was quite simple, so what if we add a third coin?  How many ways can we make 200p using 1p, 2p and 5p pieces?  We have an analog to the 2 coin case here.  If we know how many 5p pieces we are using can we determine the number of ways to make the remaining change with only 1 and 2 pence pieces?  To answer this critical question let's introduce the following notation.
$$p_k(n)=\text{the number of ways to make }n\text{ pence using coins of value }\leq{k}.$$

For example $p_1(n)=1$ for all $n$ because there is only one way to make any amount of change only using the 1p pieces.
How about $p_2(n)$?  Here we can do casework.  Above we solved a specific case  ($p_2(200)$) by dividing into cases depending on how many $2p$ pieces we used.  In general, $p_2(n)$ satisfies the recurrence $$p_2(n)=p_1(n)+p_1(n-2)+p_1(n-4)+...+p_1(n-2\lfloor{\frac{n}{2}}\rfloor)$$
The first term being the number of ways to make $n$ pence if we used no 2p pieces, the second term being the number of ways if we used 1, the third term if we used 2, etc. And the last term being if we used the maximum allowable number of 2p pieces.  It's clear that there is nothing special about the fact we are using 2p pieces here and we could in fact make the same argument for 5p pieces and derive an expression of the form $$p_5(n)=p_2(n)+p_2(n-5)+p_2(n-10)+...+p_2(n-5\lfloor{\frac{n}{5}}\rfloor).$$
Here the skip from 5 to 2 is because there is no 3p piece and no 4p piece.  This gives us an outline for an argument we can use for any coinage amount.
On your own you might try deriving the expression for 10p pieces and above.

All said and done here is an example of the code we might get  solving this problem:

Now this solves the particular case from the Project Euler site. Running the code tells us the total number of ways to make $£2$ using the above coin combinations is $73,682$!