# Settlers of Catan Probability: How many Resource Cards to get Victory Point?

Settlers of Catan asks its players to understand a bit of probability. For example, players generally understand that the “number of dots” is related to the probability of rolling the corresponding number on a pair of dice by a constant factor such that the number of dots is additive. Another topic that has gotten some attention is the expected number of resources required to draw a victory point from development cards. There is a large variance on what players expect it to be, and most of them appear to be incorrect.

To avoid explaining the gameplay, we will use the analogy of how many draws it takes to draw an Ace from a normal deck of cards.

With replacement, the answer is simple. It is 13 as you might expect. You draw it with a $\frac{1}{13}$ probability, so it will on average take 13 draws. To prove this use recursion (i.e. $X\ = \ 1\ \left( \frac{1}{13} \right)\ + \ X\ \left( \frac{12}{13} \right)$ where $X$ is the answer we need).

Without replacement, the answer is more complicated. The easier approach is approximation by a continuous case. Assume $X_{1},\ X_{2},\ X_{3},\ X_{4}$ are independently and uniformly distributed between 0 and 1, which represents the position of each of the cards. The CDF that $max\ (X_{1},\ X_{2},\ X_{3},\ X_{4})\ < \ X$ is simply $X^{4}$, which has an expectation of $\frac{4}{5}$. That tells you that the approximation of the case without replacement is $13\ *\frac{4}{5} = \ 10.4$. An excel approximation would tell you the answer is 10.6 which is really quite close. You will find that the more cards are added to the deck, the closer we begin converging to the $\frac{4}{5}$ number.

Now, the actual solution without replacement. We need to visualize the deck of 48 non-Ace cards in a circle. We then need to envision these 48 cards split up by the four Aces and the one “cut-of-the-deck” (the starting point). It should be fairly clear that all arrangements of the 48 cards + 5 cuts are equally likely (indeed this is the definition of what statisticians call the hypergeometric distribution). But effectively, when you split 48 cards with 5 cuts, the average distance between any two cuts should be 48/5 cards (see comment below for discussion). Adding in the fact the 2nd cut is a card in itself, the answer is $\frac{48}{5} + \ 1\ = \ 10.6$.

Taking this back to the Settlers of Catan example, we calculate that it takes 5.2 draws or 15.6 resource cards to get victory point, which some people would view as too high of a cost. (I.e. it is neither the 12 nor 18 cited by certain literature).

Further Discussion:

When you split 48 cards with 5 cuts, the average distance between any two cuts should be 48/5 cards. This is actually not entirely clear but you can probably convince yourself of this. When you do linear transformations such as divide 48 by 5, you are implicitly assuming independence between events. The reason the "with replacement" problem is so simple is because since each draw is independent, we can simply divide 52 by 4. However, when we changed to a "without replacement," this was no longer possible since each draw became dependent of one another. This is why the problem needed to be reformulated where the scenarios we imagine all happen to be independent of each other.

A lot of the analysis that is seen online is wrong because it either considers the draws to be with replacement. Another analysis we had seen was the "median" is 12 resources. Although medians are a useful measure of an average, it is not what the question is asking for. Because the number of turns has a long tail, although you are just likely to use fewer than 12 resources as you are to use more than 12 resources, there is a also a 25% probability that you will need more than 24 resources, which is a real cost that needs to be considered.

I find it interesting that the adjustment factor of going from with to without replacement as being $\frac{1}{n + 1}$ where $n$ is the number of aces. Mathematically, it is created by the integration of $x^{n}$. Visually, we can think of it as dividing up a deck card with the $n$ aces and extra "cut of the deck". So the difference between with and without replacement is effectively the fact that we need to specify a starting point, resulting in the +1.