Recursive calculation - How would it be started?

151 Views Asked by At

First off, let me assure you that this is my very last resource. I have tried everything, because I understand that posting a question that needs a hyperlink to be understood is annoying. But I would truly, truly appreciate some help in just getting the calculation started.

The post is this, and it deals with the expected number of dice rolls before all sides are seen three times. A recursive formula is generated:

$$e(\mathbf{i}) = \frac{d + i_1 e(\mathbf{i}\cdot 1) + \cdots + i_n e(\mathbf{i}\cdot n)}{d - i_0}$$

which I interpret as follows:

  1. The vector $\mathbf{i}$ is $\small [\text{no. of sides we need to see 0 times;}\,\,\,\text{no. sides need to see 1 time;}\,\,\,\text{no. sides need to see 2 times;}\,\,\,\text{no. sides need to see 3 times}]=[i_0,i_1,i_2,i_3]=[0;\,0;\,0;\,6]$.

    The entries in the vector $\mathbf{i}$, $i_j$ indicating the $\text{no. of }\color{blue}{\text{die faces}} \text{ that need to be seen } j \text{ times}.$ And $j$ ranging from $1$ to $n=3$ indexing the $\text{no. of } \color{red}{\text{times}} \text{ we need to see } i_j \text{ faces}.$

  2. So $e(\mathbf{i})$ is the expectation of such an event: all sides being seen three times.

  3. $\mathbf{i}\cdot j$ is defined as the operation that brings the $\mathbf i$ from $[0,0,0,6]$ to $[0,0,1,5]$ when any face appears; and from $[0,0,1,5]$ to $[0,1,0,5]$ if the same die happens to appear on the second roll, etc.

  4. Every transition between $\mathbf i$ vectors will occur with probability $i_j/\text{no. sides}.$

Again, my most profuse apologies for the painful introduction.

Here is the question:

How would one start this frightening computation if condemned to do it manually? To begin with, we see that in the formula there are expectations on the RHS and LHS of the equation. I guess we could write down all possible transitions in a maddening tree.

It is also unclear to me why there is a $1$ built-in the equation. But in any event, I know that there is a way to tackle this calculation and get to the figure of $32.677$:

$$e(0,0,0,6) = \frac{2\,286\,878\,604\,508\,883}{69\,984\,000\,000\,000}\approx 32.677.$$


NOTE TO SELF

1

There are 1 best solutions below

6
On BEST ANSWER

The formula $$ e(\mathbf{i}) = \frac{d + i_1 e(\mathbf{i}\cdot 1) + \cdots + i_n e(\mathbf{i}\cdot n)}{d - i_0} $$ features a function $e$ which takes a $n+1$ vector $i = (i_0, \dotsc, i_n)$. That funny notation $i \cdot n = f(i, j)$ takes a $n+1$ vector $i$ and some index $j$ and computes another $n+1$ vector.

So computing $e$ for $i = (0,0,0,6)$ will need a bunch of evaluations of $e$ for different $i$ vectors, those that result from those dot operations $f$.

The recursion seems to stop when at some point $e(d,\cdot,\cdot,\cdot)$ is reached, which seems to be $0$.

So $$ e(\mathbf{i}) = \begin{cases} 0 & \text{if } i = (d,\dotsc) \\ \frac{d + i_1 e(\mathbf{i}\cdot 1) + \cdots + i_n e(\mathbf{i}\cdot n)}{d - i_0} & \text{else} \end{cases} $$ has to implemented and called for $i = (0,0,0,6)$. A language with arbitrary long integer arithmetic support should be used.

Update:

I told that whole story to my friend Ruby, see here. She gave this answer.

The important line, which prevents infinite recursion, has the comment "important" attached to it.