Let's say we roll a fair $d$-sided die, and if the die rolls $x$ or higher, we add 1 to the success count (let's define this as $h$) and roll again, but if we roll $y$ or lower, we subtract one from the success count and roll again, and if we roll between $x$ and $y$, we stop rolling.
So, we have three potential outcomes of any given roll:
- $P$, which has a probability of $\frac{d-x+1}{d}$, adds $1$ to $h$ and has us roll again.
- $N$, which has a probability of $\frac{y}{d}$ subtracts $1$ from $h$, and has us roll again
- $S$, which has a probability of $\frac{x-y-1}{d}$ and halts the game.
I have two questions I want help on: How can we calculate the probability of an arbitrary score in this game? And how do we generalise this to $m$ dice (where we start with $m$ dice, rerolling each die until that die hits the stop outcome, with $h$ being the accumulated score of all dice)?
I can build a probability generating function for this problem, and indeed it's not particular hard:
$$F(z)=\frac{x-y-1}{d}+\frac{(d-x+1)zF(z)}{d}+\frac{yz^{-1}F(z)}{d}$$
We can then unroll the recursion into:
$$F(z)=\frac{x-y-1}{d-(d-e+1)z-yz^{-1}}$$
The problem is converting this into a Mass Function. We seem to have a Geometric component to the distribution that has two potential outcomes, that even for a single die, there's an infinite number of potential outcomes that can result in any given $h$ - any roll that ends with $h$ more $P$ outcomes than $N$ outcomes needs to be counted, and I'm not clear on the best approach to doing this, let alone what the appropriate strategy would be for $n$ dice.
The idea is to first construct a vector-valued random variable that counts the number of successes and failures observed until the stopping criterion is met. Let $(P,N)$ be an ordered pair of nonnegative integers that counts the random number of successes and failures obtained. Additionally, for convenience, let $\theta$ represent the probability of success for a single trial, and $\phi$ be the probability of failure, such that $\theta + \phi < 1$. Then $1 - \theta - \phi$ is the probability of stopping. Consequently, $$\Pr[(P = p) \cap (N = n)] = \binom{p+n}{p} \theta^p \phi^n (1-\theta-\phi), \quad p, n \in \{0, 1, 2, \ldots \}.$$ We reason that a particular sequence of $p$ successes and $n$ failures, followed by a stopping roll, has probability of $\theta^p \phi^n (1-\theta-\phi)$ of occurring; however, there are $\binom{p+n}{p}$ such sequences, each equally probable. As an exercise for the reader, one may confirm that $$\sum_{p=0}^\infty \sum_{n=0}^\infty \Pr[(P = p) \cap (N = n)] = 1.$$ The next step is to compute the net score, which is $X = P - N$. This corresponds to $$\begin{align} \Pr[X = x] &= \Pr[P - N = x] \\ &= \sum_{n=\max(0,-x)}^\infty \Pr[(P = x + n) \cap (N = n)] \\ &= \sum_{n=\max(0,-x)}^\infty \binom{x+2n}{n} \theta^{x+n} \phi^n (1-\theta-\phi) \\ &= \frac{1-\theta-\phi}{\sqrt{1 - 4 \theta \phi}} \begin{cases} \left(\frac{2\theta}{1 + \sqrt{1 - 4 \theta \phi}}\right)^x, & x \ge 0 \\ \left(\frac{1 + \sqrt{1 - 4 \theta \phi}}{2\phi} \right)^x, & x < 0 \end{cases} \\ &= \frac{1-\theta-\phi}{\sqrt{1 - 4 \theta \phi}} \left( \frac{2(\theta \mathbb 1 (x \ge 0) + \phi \mathbb 1 (x < 0))}{1 + \sqrt{1 - 4 \theta \phi}} \right)^{|x|}. \end{align}$$
What this tells us is that $X$ is a kind of generalized double geometric distribution. Here are some plots of $\Pr[X = x]$ for various values of $\theta, \phi$: