Probability of getting a specific set of rolls atleast once after n dice rolls.

Question

I am trying to calculate average number of turns it will take to win in Catan given a set of hexes.

I am stuck at calculating probability of an event given n rolls. Each roll uses 2 6-sided dice. You get a resource if a specific number(sum of 2 dice) rolls.

Say probability of getting an ore in a dice roll is x/36 and probability of getting a wheat is y/36 You can construct a city if you have accumulated 3 ore and 2 wheat.

What is the probability of being able to construct a city after (n) dice roles assuming no loss/discarding of resources?

Answer 1

If $n\leqslant 4$, then clearly it's $0$. Otherwise, note that $$ \mathbb{P}(\text{exactly i ores and j wheat after n rolls})=\frac{n!}{i!j!(n-i-j)!}\left(\frac{x}{36}\right)^i\left(\frac{y}{36}\right)^j\left(1-\frac{x+y}{36}\right)^{n-i-j} $$ as you can have different orders of occurrence of the ores/wheat/neither in your $n$ dice rolls, each of which occurs with probability $\left(\frac{x}{36}\right)^i\left(\frac{y}{36}\right)^j\left(1-\frac{x+y}{36}\right)^{n-i-j}$. Now consider when we will be unable to construct a city. If we have $0,1,2$ ores at the end, then regardless of number of wheat we can't; if we have $3,4,\ldots,n-1$ ores, then we are unable to only if we have $0,1$ wheat; if we have exactly $n$ ores, then we are again unable to. Any other combination of wheat/ore amount will be fine, so the desired probability becomes (unless I have missed something) $$ 1-\sum_{i=0}^{2}\sum_{j=0}^{n-i}\mathbb{P}(\text{i ores} \cap \text{j wheat})-\sum_{i=3}^{n-1}\sum_{j=0}^{1}\mathbb{P}(\text{i ores} \cap \text{j wheat})-\mathbb{P}\text{(n ores} \cap \text{0 wheat)} $$ which is possible to compute given $n,x,y$.

Answer 2

For a direct approach: assuming you only have a single settlement on ore and a single settlement on wheat, and no other source of these (e.g. trading, port, dev cards)... perhaps the easiest approach is via markov chains.

You have $12$ different possible states you can be in, $(0,0), (0,1), (0,2), (1,0), (1,1),\dots (3,2)$. For convenience sake, rearrange the list to put the $(3,2)$ in the front.

You have the following transition matrix:

$$A = \begin{bmatrix}1&0&0&0&0&0&0&0&0&\frac{x}{36}&0&0&\frac{y}{36}\\0&\frac{36-x-y}{36}&0&0&0&0&0&0&0&0&0&0&0\\0&\frac{y}{36}&\frac{36-x-y}{36}&0&0&0&0&0&0&0&0&0&0\\0&0&\frac{y}{36}&\frac{36-y}{36}&0&0&0&0&0&0&0&0&0\\0&\frac{x}{36}&0&0&\frac{36-x-y}{36}&0&0&0&0&0&0&0&0\\\vdots&&&\vdots&&\vdots&&&&&&\vdots\end{bmatrix}$$

where I have left the last several rows for you to complete as it is tedious to write it all down. The $r$'th row $c$'th column entry corresponds to the probability of moving from the $c$'th state to the $r$'th state. For instance, to move from the state of having three ore and one wheat to the state of having three ore and two wheat occurs with probability $\frac{y}{36}$ so the $1$'st row $12$'th column entry of the matrix is $\frac{y}{36}$. Moving from $2$ wheat to more wheat does not change the fact that we have three wheat and for the purposes of this problem we don't keep track of excess.

Now... that is what the matrix $A$ is. The matrix $A^n$ will correspond to the probabilities of moving from a particular state to another after $n$ rounds.

The probability you are interested in then? It will be the first row second column entry of $A^n$ (since we begin the game with no resources).

This matrix can share a great deal more information as well. It is an absorbing transition matrix of the form $\left[\begin{array}{c|c}I&S\\\hline 0&R\end{array}\right]$. The "fundamental" of it, $S(I-R)^{-1}$ has information in it of the expected time until the markov chain reaches an absorbing state. Again, as we are starting with no resources, the entry corresponding to the state $(0,0)$ is what will interest us, the value in the first position then is the expected wait time.

---

For a less direct approach, try asking the probability of you not having enough resources. This still is rather case heavy, but less so than more direct approaches.

If you have too few wheat is that you had zero wheat rolls or exactly one wheat roll in your $n$ rolls. That occurs with probability $(1-\frac{y}{36})^n + n(\frac{y}{36})(1-\frac{y}{36})^{n-1}$

If you have too few ore, thats if you had exactly zero, exactly one, or exactly two ore. $(1-\frac{x}{36})^n+n(\frac{x}{36})(1-\frac{x}{36})^{n-1}+\binom{n}{2}(\frac{x}{36})^2(1-\frac{x}{36})^{n-2}$

It is possible however that both of these conditions happened simultaneously and so we would need to find the probabilities of exactly no wheat and no ore, exactly one wheat and no ore, exactly no wheat and exactly one ore, exactly one wheat and one ore, etc... and subtract these away as per inclusion exclusion $|A\cup B|=|A|+|B|-|A\cap B|$.

Again, this is tedious to write out so I leave it to you to complete.