Player rolls dice: for every “1” he gets 1 point, “11” - 5 points, “111” - 10 pts, so on. What is the mean score after 100 rolls?

For $x \neq 1$:

• every $“\cdots x1x\cdots“$ gives +1 pt
• every $“\cdots x11x\cdots“$ gives +5 pts.
• every $“\cdots x111x\cdots“$ gives +10 pts.
• And so on: $n$ consecutive 1’s gives us $(n-1)5$ points.

To make it clear, the usual 6-sided dice is rolled 100 times, so for example if player rolls dice 1 time - there’s 1/6 chance of getting 1 point; rolls two times - then there’s $\frac{1}{6}\frac{5}{6}2$ chance of 1 point(“1x” or “x1”) and $\left(\frac{1}{6}\right)^2$ of getting 5 points(only if “11” rolled out). The question: what is the mean score after rolling dice 100 times?

The problem is: how do we calculate the mean when the number of rolls is so huge? It’s clear that using definition of the mean directly is not an option because number of different configurations for getting any score is immense(only if that score is not, say, 99*5 which require all the 1’s).

I tried to use induction, but it didn’t worked out, for 3-4 rolls it already gets complicated. Moreover, how am I suppose to use it? If I know mean for &n& rolls and then I add $(n+1)$th roll - it will add 0, 1 or 5 points depending on which number rolled in $n$th place. Seems like knowing mean for $n$ rolls won’t be much of a help because after one more roll chance of getting any score is different.

Another idea given to me by roommate is to fix number of ones that we get in entire 100-length sequence(so probability is fixed as well), and see what number of points we can possibly get with that number of 1’s - to know that these numbers will appear in formula for mean with known probability factor. But I’m not sure about that also because the amount of combinations is still insane.

I ran out of ideas for now. Feels like there must be some efficient, less bloody way to calculate all that because our teacher gave us only 40 minutes for that problem (and another one), which completely freaked me out. All I wanted to say - I really appreciate any of your help since I absolutely have to figure this out.

One more question: could anyone recommend some book with hard combinatorial problems in probability? Or some good textbook which could explain how to solve problems of that kind. That would be very helpful as well, thank you.

Just to give a different approach, we could use indicator variables to count the expected occurrences of blocks of exactly $n$ ones.

We note, for instance, that the expected number of singleton $1's$ is $$E_1=2\times \frac 16\times \frac 56+98\times \frac 16\times \left(\frac 56\right)^2$$

Where the first term counts the contribution from the first and last tosses and the second term counts the contribution for all the middle terms. Note that blocks in the middle must be preceded and followed by something other than $1$.

Similarly, the expected number of blocks of exactly $n$ ones is $$E_n=2\times \left(\frac 16\right)^n\times \frac 56+(99-n)\times \left(\frac 16\right)^n\times \left(\frac 56\right)^2$$

At least for $2≤n≤99$. For $100$ there's only the one possibility and we get $E_{100}=\left(\frac 16\right)^{100}$.

It follows that the answer is $$E_1\times 1 +\sum_{n=2}^{100}E_n\times 5(n-1)\approx 25.3704$$

Let $a_n$ be the expected score of $n$ rolls. Obviously $a_0 = 0$.

Let $k$ be the number of consecutive $1$'s at the beginning of the rolls. E.g. $k=0$ if the first roll is not $1$.

The probability of $k$ consecutive $1$'s at the beginning is equal to $5/6^{k+1}$ for $0\leq k <n$ and equal to $1/6^n$ for $k=n$.

In that case, the remaining rolls will give an expected score of $a_{n-k-1}$ (where $a_{-1}$ is understood to be $0$).

Thus we get the recurrence relation:$$a_n = \frac1 {6^n}(5(n-1)+1_{n=1})+\sum _{k=0}^{n-1}\frac 5 {6^{k+1}}(a_{n-k-1} + 5(k-1) + 1_{k=1} + 5\cdot 1_{k =0})$$ for all $n\geq1$.

It is then easy to show by induction that $a_n = (55n-20)/216$ for all $n\geq2$.

Therefore the answer for $100$ rolls is $685/27\approx 25.37$.

Note: This answer is the result of the analysis of already existing answers. It is mainly based upon the recurrence relation provided by @WhatsUp and could be seen as a supplement to his answer.

Denoting with $a_n, n\geq 1$ the expected number of $n$ rolls, we show the following is valid: \begin{align*} \color{blue}{a_1}&\color{blue}{=\frac{1}{6},\quad a_2=\frac{15}{6^2}}\\ \color{blue}{a_{n+1}}&\color{blue}{=a_{n}+\frac{55}{6^3}\qquad\qquad n\geq 2}\tag{1}\\ \end{align*}

We see in (1) the solution to the problem can be formulated as a rather simple non-homogeneous linear recurrence relation. It might be interesting to see how the constant $\frac{55}{6^3}$ comes into play as it is not obvious how it is related with the problem. The denominator $6^3=216$ indicates that three rolls are sufficient to determine the relation. We will see, this is the key to solve this recurrence relation.

From the recurrence relation (1) it follows easily that for $n\geq 2$ \begin{align*} a_{n+1}&=a_{n}+\frac{55}{6^3}=a_{n-1}+2\cdot\frac{55}{6^3}=\cdots=a_{2}+(n-1)\frac{55}{6^3}\\ &=\frac{15}{6^2}+(n-1)\frac{55}{6^3}\\ &=\frac{1}{6^3}\left(55n+35\right)\\ \end{align*} so that \begin{align*} \,\,\color{blue}{a_{100}}&=\frac{1}{6^3}\left(55\cdot99+35\right)\color{blue}{=\frac{685}{27}=25.\overline{370}} \end{align*} in accordance with the result stated by @WhatsUp.

In order to better see what's going on we start to manually calculating cases for small $n=2,3$ and $n=4$.

Case n=2:

We list all possible cases with corresponding weights, denoting with $1$ the roll of a $\mathbf{1}$ which occurs with probability $\frac{1}{6}$ and with dot $.$ the roll of any other number occurring with probability $\frac{5}{6}$. Skipping for better readability the factor $\frac{1}{6^2}$ and writing the probabilities of occurrence in parenthesis, we have

\begin{align*} \begin{array}{cccclrr} a_2\qquad\qquad&.&.&\qquad&\qquad (5\cdot5) \cdot 0&=&0\\ &.&1&\qquad&\qquad (5\cdot1) \cdot 1&=&5\\ &1&.&\qquad&\qquad (1\cdot5) \cdot 1&=&5\\ &1&1&\qquad&\qquad (1\cdot1) \cdot 5&=&5\\ \hline &&&\qquad&\qquad\text{Total:}&=&15 \end{array} \end{align*}

We see the expected number in case of two rolls is $\frac{15}{6^2}$ showing the initial conditions of the recurrence relations are valid, since $a_1=\frac{1}{6}$ is obvious.

When listing the next cases for $n=3$ to find $a_3$ we will also indicate a relationship with $a_2$. We do so by appending a dot $.$ to the RHS of the cases of $a_2$ and then by appending a $\mathbf{1}$ to them. We obtain

Case n=3:

\begin{align*} \begin{array}{cccccclrr} a_3\quad&.&.&.&\quad&&\quad (5^3\cdot1^0) \cdot 0&=&0\\ &.&1&.&\quad&&\quad (5^2\cdot1^1) \cdot 1&=&25\\ &1&.&.&\quad&\frac{5}{6}a_2&\quad (5^2\cdot1^1) \cdot 1&=&25\\ &1&1&.&\quad&&\quad (5^1\cdot1^2) \cdot 5&=&25\\ \hline &.&.&1&\quad&&\quad (5^2\cdot1^1) \cdot (0\color{blue}{+1})&=&0\color{blue}{+5^2\cdot 1}\\ &.&1&1&\quad&&\quad (5^1\cdot1^2) \cdot (1\color{blue}{+4})&=&5\color{blue}{+5^1\cdot 4}\\ &1&.&1&\quad&\frac{1}{6}a_2+\frac{1}{6^3}\color{blue}{C}&\quad (5^1\cdot1^2) \cdot (1\color{blue}{+1})&=&5\color{blue}{+5^1\cdot 1}\\ &1&1&1&\quad&&\quad (5^0\cdot1^3) \cdot (5\color{blue}{+5})&=&5\color{blue}{+5^0\cdot 5}\\ \hline &&&&\quad&\quad&\text{Total:}&=&6\cdot15\color{blue}{+55}=145 \end{array} \end{align*}

We see the upper half of the table does not change any number of $\mathbf{1}$s and so the weights are the same as for $a_2$. To get the expected occurrence we simply have to multiply $a_2$ by $\frac{5}{6}$. The lower half of the table has a $\mathbf{1}$ appended to the RHS which changes the weight. This change is marked blue, so that we can separate the part $\frac{1}{6}a_2$ which comes from the first two rolls and an additive part respecting the appended $\mathbf{1}$.

We will see this pattern \begin{align*} \color{blue}{C=5^2\cdot 1+5^1\cdot 4+5^1\cdot 1+5^0\cdot 5=55} \end{align*} occurs in all following cases.

Case n=4:

It is sufficient to list the $8$ of $16$ cases which have a $\mathbf{1}$ appended at the RHS, since we know from $n=3$, that appending dot ($\mathbf{2}$ to $\mathbf{6}$) does not change the number of $\mathbf{1}$s. We obtain in this case as before $\frac{5}{6}a_3$. Now the interesting part:

\begin{align*} \begin{array}{ccccccclrr} a_4&.&.&.&.&\,&&\,(5^4\cdot1^0) \cdot 0&=&0\color{blue}{+5^2\cdot 1}\\ &&&\cdots&&\,&\frac{5}{6}a_3&\,\cdots&=&5\cdot 145\quad\quad\quad\quad\\ &1&1&1&.&\,&&\,(5^1\cdot1^3) \cdot 10&=&25\color{blue}{+5^1\cdot 1}\\ \hline &.&\color{blue}{.}&\color{blue}{.}&\color{blue}{1}&\,&&\,(5^3\cdot1^3)\cdot(0\color{blue}{+1})&=&0\color{blue}{+5^2\cdot 1}\\ &.&\color{blue}{.}&\color{blue}{1}&\color{blue}{1}&\,&&\,(5^2\cdot1^2) \cdot (1\color{blue}{+4})&=&25\color{blue}{+5^1\cdot 4}\\ &.&\color{blue}{1}&\color{blue}{.}&\color{blue}{1}&\,&&\,(5^2\cdot1^2) \cdot (1\color{blue}{+1})&=&25\color{blue}{+5^1\cdot 1}\\ &.&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\,&\frac{1}{6}a_3+\frac{1}{6^3}D&\,(5^1\cdot1^1)\cdot(5\color{blue}{+5})&=&25\color{blue}{+5^0\cdot 5}\\ &1&.&.&1&\,&&\,(5^2\cdot1^2)\cdot(1\color{blue}{+1})&=&25\color{blue}{+5^2\cdot 1}\\ &1&.&1&1&\,&&\,(5^1\cdot1^1)\cdot(2\color{blue}{+4})&=&10\color{blue}{+5^1\cdot 4}\\ &1&1&.&1&\,&&\,(5^1\cdot1^1)\cdot(5\color{blue}{+1})&=&25\color{blue}{+5^1\cdot 1}\\ &1&1&1&1&\,&&\,(5^0\cdot1^0)\cdot(10\color{blue}{+5})&=&10\color{blue}{+5^0\cdot 5}\\ \hline &&&&&\,&&\text{Total:}&=&6\cdot145\color{blue}{+6\cdot 55}=1\,200 \end{array} \end{align*}

Observe the blue marked group on the left side in the first half of the table is a copy from the table of $a_3$. In fact it is copied here twice. Once when doing the $\frac{5}{6}a_3$ related stuff which adds $5$ times $55$ and once when doing the $\frac{1}{6}a_3$ related stuff which adds $1$ times $55$ giving a total of $6\cdot 55$. Since we did one more roll when going from $a_3$ to $a_4$ we have to multply with $\frac{1}{6}$ giving us again \begin{align*} D = \frac{1}{6}\cdot\left(6\cdot 55\right) = C = 55 \end{align*}

Conclusion: This blue marked group is the relevant pattern which is doubled each step when going from $a_n$ to $a_{n+1}, n\geq 2$. The three columns of this pattern represent three rolls which contain all the information for the constant value $\color{blue}{55}$.

Notes:

• The numbers $a_1=\frac{1}{6}, a_2=\frac{15}{6^2}, a_3=\frac{15}{6^3}=\frac{145}{6^3}$ and $a_4=\frac{1\,200}{6^4}$ are in line with the numbers stated by @QC_QAOA.

• The recurrence relation (1) can also be derived from the recurrence relation stated by @WhatsUp.

Recurrence relation from @WhatsUp: We write the recurrence relation in the form \begin{align*} \color{blue}{a_0}&\color{blue}{=0,\quad a_1=\frac{1}{6}}\\ \color{blue}{a_{n}}&\color{blue}{=\frac{1}{6^n}5(n-1)+\frac{5}{6}a_{n-1}+\frac{5}{6^2}\left(a_{n-2}+1\right)}\\ &\qquad\color{blue}{+\sum_{k=2}^{n-1}\frac{5}{6^{k+1}}\left(a_{n-k-1}+5(k-1)\right)\qquad\qquad n\geq 2} \tag{2} \end{align*}

The first summand of the RHS in (2) represents an $n$-run of $1$s which is weighted with $5(n-1)$. The second stands for the expection of starting with a number not equal to $\mathbf{1}$ leaving us with the factor $a_{n-1}$. The third one stands for $\mathbf{1\ .}$ weighted with $1$ and leaving us with the factor $a_{n-2}$. Then we start with $k$-runs of $1$s of length $2\leq k\leq n-1$.

Looking at (2) it is convenient to calculate the difference $a_{n+1}-\frac{1}{6}a_n$ since then we get rid of most of the terms $a_{n-k}$.

We obtain for $n\geq 2$: \begin{align*} \color{blue}{a_{n+1}-\frac{1}{6}a_{n}}&=\frac{5}{6^{n+1}}n+\frac{5}{6}a_n+\frac{5}{6^2}\left(a_{n-1}+1\right)\\ &\qquad+\sum_{k=2}^n\frac{5}{6^{k+1}}\left(a_{n-k}+5(k-1)\right)\\ &\qquad-\frac{5}{6^{n+1}}(n-1)-\frac{5}{6^2}a_{n-1}-\frac{5}{6^3}\left(a_{n-2}+1\right)\\ &\qquad-\sum_{k=2}^{n-1}\frac{5}{6^{k+2}}\left(a_{n-k-1}+5(k-1)\right)\\ &=\frac{5}{6^{n+1}}n+\frac{5}{6}a_n+\frac{5}{6^2}\left(a_{n-1}+1\right)\\ &\qquad+\sum_{k=2}^n\frac{5}{6^{k+1}}\left(a_{n-k}+5(k-1)\right)\\ &\qquad-\frac{5}{6^{n+1}}(n-1)-\frac{5}{6^2}a_{n-1}-\frac{5}{6^3}\left(a_{n-2}+1\right)\\ &\qquad-\sum_{k=3}^{n}\frac{5}{6^{k+1}}\left(a_{n-k}+5(k-2)\right)\tag{3}\\ &=\left(\frac{5}{6}a_n+\frac{5}{6^2}\right) +\left(\frac{5}{6^3}\left(a_{n-2}+5\right)\right)\\ &\qquad+\left(\frac{5}{6^{n+1}}-\frac{5}{6^3}\left(a_{n-2}+1\right)\right)+\left(\sum_{k=3}^n\frac{5}{6^{k+1}}5\cdot 1\right)\tag{4}\\ &=\left(\frac{5}{6}a_n+\frac{5}{6^2}\right)+\left(\frac{25}{6^3}\right)\\ &\qquad+\left(\frac{5}{6^{n+1}}-\frac{5}{6^3}\right)+\left(\frac{5}{6^3}-\frac{5}{6^{n+1}}\right)\\ &\,\,\color{blue}{=\frac{5}{6}a_{n}+\frac{55}{6^3}} \end{align*} and the claim (1) follows.

This derivation was in fact my starting point when analysing the recurrence relation of @WhatsUp which revealed the interesting constant $\frac{55}{6^3}$.

Comment:|

• In (3) we shift the index of the second sum by one to obtain summands with $a_{n-k}$ and ease this way cancellation.

• In (4) we cancel terms and group the values from the former lines to ease traceability.

Seems like I found a solution.

Since contribution of each roll is dependent on its neighbours, and the mean function is linear operator which doesn’t care about dependence - let’s assign random value to each of 100 rolls, making their sum equal to overall score.

$n_i$ denotes i-th roll; $x$ is anything that’s not 1;

Defining value $\xi_1$ which we gonna assign to 1st and 100th roll:

$$\begin{array}{c|c|} \text{$n_1n_2$} & \text{$\xi_1$} \\ \hline xx, x1 & 0 \\ \hline 1x & 1 \\ \hline 11 & 4 \\ \hline \end{array}$$

In other words, it denotes how much 1st roll adds to the sum. In case of $n_1n_2n_3 = 112, 113, \cdots$, $n_1$ gives +4 and $n_2$ gives +1.

Next we define $\xi_i$, $i = 2, 3, \cdots, 99$

$$\begin{array}{c|c|} \text{$n_{i-1}n_{i}n_{i+1}$} & \text{$\xi_i$} \\ \hline 1x1, xx1, xxx, 1xx & 0 \\ \hline x1x, 11x & 1 \\ \hline x11 & 4 \\ \hline 111 & 5 \\ \hline \end{array}$$

$S$ - score.

$$S = \xi_1 + \cdots + \xi_{100} ~ ,$$ $$ \mathbb{E}S = \mathbb{E}\xi_1 + \cdots + \mathbb{E}\xi_{100} = 2\mathbb{E}\xi_1 + 98 \mathbb{E}\xi_2 ~ ,$$

If I’m not messed up here, $\mathbb{E}\xi_1 = 1/4$ and $\mathbb{E}\xi_2 = 55/216$, so the answer is

$\frac{1}{2} + 98\frac{55}{216} \approx 25,45$

(wow, which even correlates with QC_QAOA’s machinery answer in the comments)

This is not an answer, but simply me checking what happens for smaller values of rolls. Note that these are exact values and not estimations as I am going through all $6^n$ different roll possibilities for $n$ rolls.

$$n=1:\ 1\cdot 6^{-1}$$

$$n=2:\ 15\cdot 6^{-2}$$

$$n=4:\ 145\cdot 6^{-3}$$

$$n=4:\ 1200\cdot 6^{-4}$$

$$n=5:\ 9180\cdot 6^{-5}$$

$$n=6:\ 66960\cdot 6^{-6}$$

$$n=7:\ 473040\cdot 6^{-7}$$

$$n=8:\ 3265920\cdot 6^{-8}$$

This tracks with @WhatsUp answer as it matches their function for the first few values.