Combinatorial identity on decreasing dice throws

Question

Suppose I repeatedly throw fair $n$-sided dice until I throw a $1$, at which point I stop.

I want to know the probability $p(n)$ that my sequence of throws will be decreasing, such as $5-4-2-1$ or just $1$ immediately, but not $2-3-1$ which would count as a failure.

The answer clearly depends on whether I am considering strictly decreasing sequences in which case $4-2-2-1$ would count as a failure, or weakly decreasing sequences in which case it would be a success. Allowing weakly decreasing sequences would increase the probability and would mean there is no bound on the potential length of successful sequences.

• For strictly decreasing sequences I have $$p_s(n)=\sum\limits_{k=1}^n {n-1 \choose k-1}\frac{1}{n^k} = \frac{(n+1)^{n-1}}{n^n}$$

• For weakly decreasing sequences and $n>1$ I have $$p_w(n)=\sum\limits_{k=1}^\infty {n+k-3 \choose k-1}\frac{1}{n^k} = \frac{n^{n-2}}{(n-1)^{n-1}}$$

For example with $n=6$, I get $p_s(6)=\frac{7^5}{6^6}\approx 0.36023$ and $p_w(6)=\frac{6^4}{5^5}\approx 0.41472$. In general $$p_s(n)=p_w(n+1).$$ Is there a combinatorial argument that leads to this equality between the finite sum and the infinite sum?

Answer 1

We can get more specific. For each subset $K\subseteq[n]$, what is the probability that the sequence will be strictly decreasing, and the set of values appearing will be $K$? Call this $p_s(n,K)$ and $p_w(n,K)$, depending on the interpretation of "decreasing."

• $p_s(n,K)=\frac1{n^{|K|}}$, obviously.

• $p_w(n,K)=\frac1n \cdot \frac1{(n-1)^{|K|-1}}$. There is a $1/n$ chance the first number rolled is the highest value of $K$. You then keep rolling until you get a different number, and the next new number has a $1/(n-1)$ chance of being the second highest value of $K$. Similarly, each subsequent new number has a $1/(n-1)$ chance of being the next value of $K$.

Using these equations, you can show that for any $K$ with $[1]\subseteq K\subseteq [n]$, $$ p_s(n,K)=p_w(n+1, K)+p_w(n+1,K\cup\{n+1\}). $$ Summing over all valid $K$, you get $p_s(n)=p_w(n+1)$.

Intuitively, when allow weakly decreasing sequences, the rerolled values can be ignored, reducing the number of sides of the die by one for all rolls except the first one. For the first roll, we have the equality $1/n=1/(n+1)+1/((n+1)\cdot n)$ which allows everything to work out.

Answer 2

By making the substitution $m=n-1$, the RHS of $p_w$ becomes the RHS of $p_s$.

Use the binomial identity to change the binomial coefficient of $p_w$ to:

$$\binom{n+k-3}{n-2}$$

The binomial coefficient of $p_w$ after the substitution represents one more die:

$$\binom{n+k-2}{n-1}$$

There is a $1-1$ mapping from the collection of throws of specific numbers in $p_w$ and the single same specific throw in $p_s$.

$\frac{1}{m^k}=\frac{1}{(n+1)^k}$ represents the adjusted probability, and $p_w$ uses the probability of an infinite run length, given by:

$$\frac{1}{n+1}+\frac{1}{(n+1)^2}+\dots$$ $$=\frac{1}{1-\frac{1}{(n+1)}}-1$$ $$=\frac{n+1}{n}-1$$ $$=\frac{1}{n}$$

Equality of $p_s$ and $p_w$ then comes from equating the two LHS's by $\frac{1}{n^k}$.