Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$.

Question

Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$).

What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ rolls lie in the set $\{1,2,\ldots,m-1\}$?

If a closed form in terms of $k,n$ cannot be easily found, a recursion would be equally useful, so it can be more easily calculated.

I have tried calculating this for specific values of $n$ and $k$, but it is difficult, because the two events corresponding to distinct values of $m$ are not mutually exclusive, so you can't just calculate the probability of the event occurring for each value of $m\leq n$, and add them up. This means that copious use of the Principle of Inclusion-Exclusion is required, and it gets messy very quickly.

Answer 1

I fiddled with this after the false-start of missing the $-1$ on $m-1$ for the set.

It appears that the desired result is $S/k^n$, where $S$ is the $(n-1)_{\text{th}}$ element of the $k_{\text{th}}$ row of $A099614$.

So, e.g,. for a six sided die rolled 4 times, $89/432$ results.

The following Mathematica snippet calculates this directly.

p[faces_, rolls_] := Numerator[(faces/(1 + faces))^rolls + rolls/(1 + faces) - 1]/faces^rolls

One can also use WolframAlpha (snip the code to the right of ":=" and replace symbols with values).

I have not found a more direct method to generate the numerator, I'm sure one probably exists.

Here's a quick plot of the calculated results against a simulation check for a 20-sided die rolled 2 to 19 times.

Answer 2

I think this seems like a hard problem because we're tempted to see $k$ as fixed and try to use induction or recursion over $n$. The proof of the formula that Hammy found is actually quite straighforward if we focus on $k$.

How many admissible sequences of $n$ rolls are there with $k$ sides, $k\ge n$? Since rolling $k$ doesn't contribute to admissibility, choose any number $j$ of rolls for an admissible sequence using only the first $k-1$ sides and fill the remaining rolls with $k$'s:

$$ a(k,n)=\sum_{j=0}^n\binom nja(k-1,j)\;. $$

This allows us to prove Hammy's formula,

$$ a(k,n)=k^n-(k+1)^n+n(k+1)^{n-1}\;, $$

by induction over $k$ and $n$. (Note that the indices in the OEIS sequence Hammy linked to are shifted and swapped with respect to ours.)

The base cases are $a(k,0)=0$ and $a(n-1,n)=(n-1)^n$, since for $n-1$ sides all sequences are admissible. These are readily checked. The induction step uses the binomial expansion of $(x+1)^n$:

\begin{eqnarray} a(k,n) &=&\sum_{j=0}^n\binom nja(k-1,j)\\ &=&\sum_{j=0}^n\binom nj\left((k-1)^j-k^j+jk^{j-1}\right)\\ &=&\sum_{j=0}^n\binom nj\left((k-1)^j-k^j+\frac{\mathrm d}{\mathrm dk}k^j\right)\\ &=&k^n-(k+1)^n+\frac{\mathrm d}{\mathrm dk}(k+1)^n\\ &=&k^n-(k+1)^n+n(k+1)^{n-1}\;. \end{eqnarray}