The expected value of $C$ is equal to $\frac{a}{b}$ for coprime positive integers $a$ and $b.$ What is $a+b?$

Question

A fair, $6$-sided die is rolled $20$ times, and the sequence of the rolls is recorded.

$C$ is the number of times in the 20-number sequence that a subsequence (of any length from one to six) of rolls adds up to $6.$ These subsequences don't have to be separate and can overlap each other. For example, the sequence of $20$ rolls $ 12334222111366141523 $ contains the ten subsequences $123, 33, 42, 222, 2211, 1113, 6, 6, 141, 15$ which all add up to $6,$ so $C=10$ in this case.

The expected value of $C$ is equal to $\frac{a}{b}$ for coprime positive integers $a$ and $b.$

What is $a+b?$

Suppose that a total of $N \ge 6$ dice are rolled. For integers $1 \le u \le 6$ and $u \le v \le N$, let $X_{uv}$ be the indicator random variable that is equal to $1$ if a consecutive subsequence of $u$ dice rolls (ending with the $v$th in the main sequence) adds to $6$, and which is equal to $0$ otherwise. Thus how should I continue to solve this?

I know the answer is 13733 but I want to know what is the solution for this.

Answer 1

There is $1$ way to make a $6$ with a $1$-digit subsequence (with a $6$), out of a total of $6$ $1$-digit combinations, and there are $20$ $1$-digit subsequence in the $20$-digit sequence, for an expected value of $\frac{1}{6}\cdot 20 = \frac{10}{3}$.

There are $5$ different ways to make a $6$ with a $2$-digit subsequence (with a $15$, $24$, $33$, $42$, or $51$), out of a total of $6^2$ $2$-digit combinations, and there are $19$ $2$-digit subsequences in the $20$-digit sequence, for an expected value of $\frac{5}{6^2}\cdot 19 = \frac{95}{36}$.

There are $10$ different ways to make a $6$ with a $3$-digit subsequence (with the digits of $114$ there are $\frac{3!}{2!} = 3$ ways, with the digits of $123$ there are $3! = 6$ ways, and with the digits of $222$ there is $\frac{3!}{3!} = 1$ way, for a total of $3 + 6 + 1 = 10$ different ways), out of a total of $6^3$ $3$-digit combinations, and there are $18$ $3$-digit subsequences in the $20$-digit sequence, for an expected value of $\frac{10}{6^3}\cdot 18 = \frac{5}{6}$.

There are $10$ different ways to make a $6$ with a $4$-digit subsequence (with the digits of $1113$ there are $\frac{4!}{3!} = 4$ ways, with the digits of $1122$ there are $\frac{4!}{2!2!} = 6$ ways, for a total of $4 + 6 = 10$ different ways), out of a total of $6^4$ $4$-digit combinations, and there are $17$ $4$-digit subsequences in the $20$-digit sequence, for an expected value of $\frac{10}{6^4}\cdot 17 = \frac{85}{648}$.

There are $5$ different ways to make a $6$ with a $5$-digit subsequence (with the digits of $11112$ there are $\frac{5!}{4!} = 5$ ways), out of a total of $6^5$ $5$-digit combinations, and there are $16$ $5$-digit subsequences in the $20$-digit sequence, for an expected value of $\frac{5}{6^5}\cdot 16 = \frac{5}{486}$.

Finally, there is $1$ way to make a $6$ with a $6$-digit subsequence (with a $111111$), out of a total of $6^6$ $6$-digit combinations, and there are $15$ $6$-digit subsequences in the $20$-digit sequence, for an expected value of $\frac{1}{6^6}\cdot 15 = \frac{5}{15552}$.

The combined expected value is $\frac{10}{3} + \frac{95}{36} + \frac{5}{6} + \frac{85}{648} + \frac{5}{486} + \frac{5}{15552} = \frac{12005}{1728}$, so $a = 12005$ and $b = 1728$, and $a + b = \boxed{13733}$.

Answer 2

My solution for this is

$ X_{uv} \; = \; \left\{ \begin{array}{lll} 1 & \hspace{1cm} & d_v + d_{v-1} + ... + d_{v+1-u} = 6 \\ 0 & & \mathrm{ow} \end{array}\right. $ where $d_k$ is the value of the $k$th die roll for $1 \le k \le N$. Then $ C \; = \; \sum_{u=1}^6 \sum_{v=u}^N X_{uv} $ and hence, by the linearity of expectation, $ \mathbb{E}[C] \; = \; \sum_{u=1}^6 \sum_{v=u}^N \mathbb{E}[X_{uv}] \; = \; \sum_{u=1}^6 \sum_{v=u}^N \mathbb{P}[X_{uv} = 1] $ Now $\mathbb{P}[X_{uv} = 1]$ is the probability that the sum of $u$ dice rolls is equal to $6$, and hence is $\frac{n_u}{6^u}$, where $n_u$ is the number of ways in which $u$ dice rolls can total $6$, which is the coefficient of $x^6$ in the expansion of $(x + x^2 + x^3 + x^4 + x^5 + x^6)^u$. Since $ x + x^2 + x^3 + x^4 + x^5 + x^6 \; = \; \frac{x(1-x^6)}{1-x} $ we see that $n_u$ is the coefficient of $x^6$ in $x^u(1-x)^{-u}$, and hence is the coefficient of $x^{6-u}$ in $(1-x)^{-u}$. Thus we deduce that $ n_u \; = \; {u + (6-u) - 1 \choose u-1} \; =\; {5 \choose u-1} \hspace{2cm} 1 \le u \le 6 $ Therefore $ \begin{align} \mathbb{E}[C] & = \sum_{u=1}^6 \sum_{v=u}^N \frac{n_u}{6^u} \; = \; \sum_{u=1}^6 \frac{n_u(N+1-u)}{6^u} \; = \; \sum_{u=1}^6 \frac{N+1-u}{6^u}{5 \choose u-1} \\ & = \sum_{u=0}^5 \frac{N-u}{6^{u+1}}{5 \choose u} \; = \; \tfrac16N\left(1 + \tfrac16\right)^5 - \tfrac{5}{36}\left(1 + \tfrac16\right)^4 \\ & = \frac{2401(7N-5)}{46656} \end{align}$ In particular, when $N=20$ we have $\mathbb{E}[C] = \frac{12005}{1728}$, making the answer $12005 + 1728 = \boxed{13733}$.