The Expected Value of "Descending Dice Problem" and Harmonic Numbers

Question

I named the "Descending Dice Problem", but not sure if there is another name to it. This is how it goes:

You start with a N sided dice. Throw it, suppose you rolled R as your result, and then throw another dice with R sides. Continue this process until you get a 1. You only roll one dice at a time. Once you rolled a dice and got a number different from 1 you forget about this dice and then only focus on the next one.

What is the expected value of dice rolls until I get a 1 if I started with a N sided dice?

I searched just for the problem's description and find nothing. Even less about its solution. After some days of thinking I got the exact result for the $N = 2, 3, 4$ cases and started looking for patterns. It seems that the solution is:

$E(Dice(n)) = 1 + H(n-1)$

Where $H(n)$ is the n-th Harmonic Number.

After checking with some python code the results were pretty much exact. Can you help me prove that this is actually the formula?

Answer 1

It gave me pleasure a good morning long. I felt the recursion but I couln't write it down. So I studied the first seven cases to find a pattern.

Let $n$ be the number of sides of the die, and $E_n$ the expected value of the "stopping time" in question.

Then I found in a cumbersome way that

$$E_n = 1 + H_{n-1}\tag{1}$$

But on my way, by detailed inspection, I also found expressions for the probability $p(n,t)$ that the process stops at step $t$. These were not requested in the OP. But they look nice, and here are some of them:

$$p(2,t) = \frac{1}{2}\frac{1}{2^{t-1}}= \frac{1}{2^t}\tag{2a}$$

$$p(3,t) = \frac{1}{3} \sum _{i=0,j=0\\i+j=t-1}^{t-1} \frac{1}{2^i 3^j}=2 \left(\frac{1}{2^t}-\frac{1}{3^t}\right)\tag{2b}$$

$$p(4,t) = \frac{1}{4} \sum _{i..k=0\\\sum i..k=t-1}^{t-1} \frac{1}{2^i 3^j 4^k}=3 \left(\frac{1}{2^t}-\frac{2}{3^t}+\frac{1}{4^t}\right)\tag{2c}$$

and in general

$$p(n,t) = (n-1) \sum _{k=1}^n (-1)^{k+1} \binom{n-2}{k-1}\frac{1}{(k+1)^t}\tag{3}$$

We can check that $p(n,t)$ is a valid probability:

$$\sum _{t=1}^{\infty }p(n,t) = (n-1) \sum _{k=1}^n (-1)^{k+1} \binom{n-2}{k-1}\sum _{t=1}^{\infty } \frac{1}{(k+1)^t}\\ =(n-1) \sum _{k=1}^n (-1)^{k+1} \binom{n-2}{k-1}\frac{1}{k} = 1\tag{4}$$

and using

$$\sum _{t=1}^{\infty } \frac{t}{(k+1)^t}=\frac{k+1}{k^2}$$

the expectation becomes

$$E(n) =\sum_{t=1}^{\infty} t p(n,t)= (n-1) \sum_{k=1}^{n} (-1)^{k+1} \binom{n-2}{k-1}\frac{k+1}{k^2}\\ =\psi ^{(0)}(n)+\gamma +1=1+ H_{n-1}\tag{5}$$

As a bonus we can also calculate the second moment

$$<t^2> = \sum_{t=1}^ {\infty} t^2\;p(n,t) =\left(H_{n-1}\right){}^2+3 H_{n-1}+H_{n-1}^{(2)}+1\tag{6a}$$

And the central second moment is simply

$$<t^2>-<t>^2 = H_{n-1}+H_{n-1}^{(2)}\tag{6b}$$

Appendix

§1. Derivation of sums in connection with $(2)$

Consider the sequence of sums

$$S_2(t,a,b):=\sum_{i,j=0}^{t-1}\delta_{i+j,t-1}a^i b^j=\sum_{i=0}^{t-1}a^i b^{t-1-i}= b^{t-1}\sum_{i=0}^{t-1}(\frac{a}{b})^i \\ =b^{t-1}\left(\frac{1-(\frac{a}{b})^t}{1-\frac{a}{b}} \right)=\frac{1}{b-a}\left(b^t- a^t\right)$$

The next sum is calculated recursively using $S_2$

$$S_3(t,a,b,c) := \sum_{i,j,k=0}^{t-1}\delta_{i+j+k,t-1}a^i b^j c^k =\sum_{k=0}^{t-1}c^k\sum_{i,j=0}^{t-1-k}\delta_{i+j,t-1-k}a^i b^j =\sum_{k=0}^{t-1}c^kS_2(t-k,a,b)\\ = \sum_{k=0}^{t-1}c^k\frac{1}{b-a}\left(b^{t-k}- a^{t-k}\right)= \sum_{k=0}^{t-1}\frac{1}{b-a}\left(b^{t}(\frac{c}{b})^k- a^{t}(\frac{c}{a})^k\right)\\ =\frac{1}{b-a}\left(b^{t}\frac{1-(\frac{c}{b})^t}{1-\frac{c}{b}}- a^{t}\frac{1-(\frac{c}{a})^t}{1-\frac{c}{a}}\right)\\ =\frac{1}{b-a}\left(\frac{b^{t}-c^{t}}{b-c}- \frac{(a^{t}-c^{t})}{a-c}\right) \\=\frac{a^{t+1}}{(a-b)(a-c)}+\frac{b^{t+1}}{(b-a)(b-c)}+\frac{c^{t+1}}{(c-a)(c-b)} $$

Similarly, we find

$$S_4(t,a,b,c,d) \\ = \frac{a^{t+2}}{(a-b) (a-c) (a-d)}+\frac{b^{t+2}}{(b-a) (b-c) (b-d)}\\ +\frac{c^{t+2}}{(c-a) (c-b) (c-d)}+\frac{d^{t+2}}{(d-a) (d-b) (d-c)}$$

The pattern is obvious, and I checked it symbolically for

$$S_5(t,a,b,c,d,f) \\= \frac{a^{t+3}}{(a-b) (a-c) (a-d) (a-f)}+\frac{b^{t+3}}{(b-a) (b-c) (b-d) (b-f)}+\frac{c^{t+3}}{(c-a) (c-b) (c-d) (c-f)}+\frac{d^{t+3}}{(d-a) (d-b) (d-c) (d-f)}+\frac{f^{t+3}}{(f-a) (f-b) (f-c) (f-d)}$$

§2. Actually, my first derivation of $(2)$ and $(3)$ was even a little bit more complicated.

I calculated the expectations from the probabilities.

This resulted in the sequence

$$E(n)|_{2}^{7} = \left\{2,\frac{5}{2},\frac{17}{6},\frac{37}{12},\frac{197}{60}\right\}$$

Had I subtracted $1$ I had probably identified the Harmonic numbers. But as I didn's I resorted to my beloved OEIS:

Its numerators

$$\{2,5,17,37,197,69\}$$

can be found here

https://oeis.org/A064168 Sum of numerator and denominator in n-th harmonic number, 1 + 1/2 + 1/3 +...+ 1/n.

and its denominators

$$\{1,2,6,12,60,20\}$$

are identified here

https://oeis.org/A002805 Denominators of harmonic numbers H(n) = Sum_{i=1..n} 1/i.

So I had found a complicated manner to express $H_{n-1}+ 1$.

Answer 2

Write $D_n$ for this sequence of random variables. More or less by definition we have

$$\mathbb{E}(D_n) = \frac{\mathbb{E}(D_1) + \dots + \mathbb{E}(D_n)}{n} + 1$$

and we can solve this recurrence as follows. Multiplying both sides by $n$ and subtracting $\mathbb{E}(D_n)$ we get $(n-1) \mathbb{E}(D_n) = \mathbb{E}(D_1) + \dots + \mathbb{E}(D_{n-1}) + n$, and substituting $n+1$ for $n$ and then subtracting gives

$$n \mathbb{E}(D_{n+1}) - (n-1) \mathbb{E}(D_n) = \mathbb{E}(D_n) + 1$$

which gives $\mathbb{E}(D_{n+1}) = \mathbb{E}(D_n) + \frac{1}{n}$. Together with the initial condition $\mathbb{E}(D_1) = 1$ we get the desired result by induction.