Calculating the probabilities of a die "weighted" by another die

Question

I don't think I have the math chops to solve this problem without heavy approximation, so I'm pitching it here. Here's the premise:

Suppose that you were to throw two N-sided dice. If the number rolled by the first die is less than or equal to that of the second, then the ultimate result of the dice roll is the number face-up on the first die. If the second die rolls a lower number, you must reroll both dice. You must continue rolling both dice until a definitive outcome is reached. Here are some examples of how this would play out with a 6-sided die:

---

First die: 4, Second die: 5 =>

4 ≤ 5 => Outcome: 4

---

First die: 2, Second die: 1 =>

2 > 1 => Outcome: Reroll =>

First die: 1, Second die: 6 =>

1 ≤ 6 => Outcome: 1

---

First die: 6, Second die: 2 =>

6 > 2 => Outcome: Reroll =>

First die: 4, Second die, 3 =>

4 > 3 => Outcome: Reroll =>

First die: 3, Second die: 3 =>

3 ≤ 3 => Outcome: 3

---

My question is this: For any value of N, is there a formula I could use to calculate the probability of any single possible outcome (e.g. chances of rolling a 13 when N = 20)? If so, what is that formula? Thank you!

Answer 1

I assume your two dice are distinguishable (for instance, they have different colors) because otherwise it doesn't make sense to talk about the "first die" and the "second die".

You pick $x$ and $y$ and throw the result out if $x > y$, so the result is equally likely to be any of the pairs $(x, y)$ with $1 \le x \le y \le n$.

The pairs with smallest value $x$ are $(x, x), (x, x+1), \ldots, (x, n)$ and there are $n - x + 1$ of them. The total number of pairs $(x, y)$ with $x \le y$ is $n(n+1)/2$. So the probability of getting $x$ with this procedure is

$${n-x+1 \over n(n+1)/2}$$

For example:

• when $n = 6$ the probability of getting $1$ is $6/21$; the probability of getting $2$ is $5/21$; and so on down until the probability of getting $6$ is $1/21$.
• when $n = 20$ the probability of getting $x = 13$, as you asked about, is $(20 - 13 + 1)/(20 \times 21 / 2) = 8/210$.

I'm guessing you have some gaming application in mind, and the idea is to have a method that's weighted towards giving the smaller numbers - if so, this works.

Answer 2

Fix an $N$, define the random variable $X$ to be the outcome of your process. You want to find its distribution, namely for each $k\leq N$ you want to find $Pr(X=k)$.

How can we find it?
For that we'll define another random variable, $Y$, which is the result of a single game (rolling both dice once), $Y$ can get the out comes $1,...,N$ and $reroll$.

Now notice that $$ Pr(X=k)=Pr(Y=k)+Pr(Y=reroll)Pr(X=k) $$ Since we can divide the event "our processes ends with k" to two disjoint smaller events:
"the processes ends on the first game and yields k" which has probabilityh of $Pr(Y=k)$
or
"the first game ends with $reroll$ and then the processes proceed and ends with $k$" which has the probability $Pr(Y=reroll)Pr(X=k)$

It's easier to calculate the distribution of $Y$. And as we saw, it will be enough for calculating the distribution of $X$.

Now The calculations :)
denote $x_k:=Pr(X=k),y_k=Pr(Y=k),\varepsilon=Pr(Y=reroll)$
we have $$x_k=y_k+\varepsilon x_k$$ so we get $$ x_k = \frac{1}{1-\varepsilon}y_k$$
$y_k=\frac{N-k+1}{N^2}$ - because only the pairs $(k,k),...(k,N)$ (out of $N^2$ possible pairs) are part of the event "output $k$ after the first game".
Calculating $\varepsilon$, notice $|A|+|B|+|C|=N^2$ where $A$ is the event "first die result is stricly grater", $B$ is the event "second die result is stricly grater" and $C$ is the event "both dice output the same number". Notice $Pr(A)=Pr(B)$ (from symmetry) and $Pr(C)=\frac{1}{N}$, hence $Pr(A)=\frac{N-1}{2N}$. Since the event $\{Y=reroll\}$ is exactly the enent $A$, we get $\varepsilon=\frac{N-1}{2N}$.

In total $$Pr(X=k)=x_k=\frac{1}{1-\varepsilon}y_k=\frac{2N}{N+1}\frac{N-k+1}{N^2}=\frac{2(N-k+1)}{N(N+1)}$$ $$\blacksquare$$