Revisit: Probabiity of X dice results in a row

Question

This is a revist of this question, which was closed because the posting was of low quality.

The original question is :

A (fair) 6 sided die is tossed $10$ times. What is the probability that somewhere in the sequence of $10$ throws, two consecutive 1's appear?

This posting is a self-answer question, which considers the following three distinct attack weapons:

• Stars and Bars Theory
• Recursion
• Inclusion-Exclusion

There may well be other viable approaches besides the three approaches above. I am posting this question because I found a few points of unusual interest:

• Inclusion-Exclusion, which generalizes well, is normally the preferred approach. I consider this problem an exception. For example, suppose, for $~k \in \{1,2,\cdots,9\},~$ you let $S_k$ denote the subset of all possible rolls where there are consecutive $1$'s on rolls $~k~$ and $~k+1~$.
  
  The difficulty comes in trying to enumerate (for example) $~\displaystyle \left\{S_1 \cap S_2\right\}, ~\left\{S_1\cap S_3\right\},~\left\{S_1 \cap S_4\right\},~ \left\{S_1 \cap S_2 \cap S_4\right\},~$ and so forth.
  So this is one of those unusual problems where Inclusion-Exclusion is not the way to go.

• Stars and Bars can be employed, in a somewhat unusal and creative manner, with reasonable elegance.

• Recursion is glaringly easy for a problem of this nature.

In the posted answer, I consequently skip Inclusion-Exclusion, and post the two distinct solutions of Stars and Bars and Recursion.

Answer 1

A (fair) 6 sided die is tossed $10$ times. What is the probability that somewhere in the sequence of $10$ throws, two consecutive 1's appear?

I will express the probability as

$$1 - \frac{N}{D} ~: ~D = 6^{10}. \tag1 $$

So, the problem has been reduced to enumerating $~N,~$ which represents the number of $10$-die-throw sequences that do not contain any occurrence of consecutive $~1$'s.

---

$\underline{\text{Method 1: Stars and Bars}}$

For Stars and Bars theory, see this article and this article.

For any satisfying (i.e. no consecutive $1$'s) sequence, there can be no more than five occurrences of a $1$, among the $10$ die throws. That is, if there are at least six $1$'s, then two of them would have to be together (i.e. consecutive).

So, you have $6$ mutually exclusive cases, since the number of $1$'s must be some element in $\{0,1,2,3,4,5\}.$ For $k \in \{0,1,2,3,4,5\}$, let $f(k)$ denote the number of satisfying rolls, that contain $k$ occurrences of a $1$.

Then

$$N = \sum_{k=0}^5 f(k). \tag2 $$

In the remainder of this section, I will:

• manually compute $f(2)$ and $f(4)$.
• use these results to develop a pattern.
• use this pattern to obtain a general formula for $f(k)$.
• plug this general formula into the expression in (2) above to obtain a numeric answer.

To compute $f(2)$, consider the number of solutions to

• $x_1 + x_2 + x_3 = (10-2) = 8.$

• $x_1, x_2, x_3 \in \Bbb{Z_{\geq 0}}$.

• $x_2 \geq 1.$

The idea is that the $2$ die rolls of $1$ create three disjoint regions, in the sequence of $(10 - 2)$ rolls that are not equal to $1$. These regions occur before the first $1$, and after each $1$. Specifying $x_2 \geq 1$ equates to not allowing the 1st and 2nd $1$'s to be right next to each other.

Setting $y_2 = x_2 - 1,$ you want the number of solutions to

• $x_1 + y_2 + x_3 = (8-1) = 7.$

• $x_1, y_2, x_3 \in \Bbb{Z_{\geq 0}}.$

Per Stars and Bars theory, you have

$$\binom {7 + 2}{2} = \binom{9}{2} ~\text{solutions}. $$

Each such solution admits $5^8$ possible values for the $8$ die throws that are not a $1$.

Therefore,

$$f(2) = \binom{9}{2} \times 5^8.$$

To compute $f(4)$, consider the number of solutions to

• $x_1 + x_2 + x_3 + x_4 + x_5 = (10-4) = 6.$

• $x_1, x_2, x_3, x_4, x_5 \in \Bbb{Z_{\geq 0}}$.

• $x_2,x_3,x_4 \geq 1.$

The idea is that the $4$ die rolls of $1$ create five disjoint regions, in the sequence of $(10 - 4)$ rolls that are not equal to $1$. These regions occur before the first $1$, and after each $1$. Specifying $x_2,x_3,x_4 \geq 1$ equates to not allowing any of the $1$'s to be right next to each other.

Setting $~y_i = x_i - 1,~ : ~i \in \{2,3,4\},~$ you want the number of solutions to

• $x_1 + y_2 + y_3 + y_4 + x_5 = (6-3) = 3.$

• $x_1, y_2, y_3, y_4, x_5 \in \Bbb{Z_{\geq 0}}.$

Per Stars and Bars theory, you have

$$\binom {3 + 4}{4} = \binom{7}{4} ~\text{solutions}. $$

Each such solution admits $5^6$ possible values for the $6$ die throws that are not a $1$.

Therefore,

$$f(4) = \binom{7}{4} \times 5^6.$$

There is now a clear pattern for computing $f(k)$.

The equation

$$x_1 + \cdots + x_{k+1} = (10 - k)$$

changes to

$$x_1 + y_2 + \cdots + y_k + x_{k+1} = (10 -k) - (k-1) = 11 - 2k,$$

so that there are

$$\binom{[11 - 2k] + k}{k} = \binom{11 - k}{k} ~\text{solutions}.$$

Therefore,

$$f(k) = \binom{11 - k}{k} \times 5^{(10 - k)}.$$

So,

$$N = \left[\binom{11}{0} \times 5^{(10)}\right] + \left[\binom{10}{1} \times 5^{9}\right] + \left[\binom{9}{2} \times 5^{8}\right]$$

$$ + \left[\binom{8}{3} \times 5^{7}\right] + \left[\binom{7}{4} \times 5^{6}\right] + \left[\binom{6}{5} \times 5^{5}\right]$$

$$ = 48,300,000.$$

---

$\underline{\text{Method 2: Recursion}}$

Let $~f(n,1)~$ denote the number of satisfying die rolls (i.e. no consecutive $1$'s) of length $n$ that end in $1$.

Let $~f(n,2)~$ denote the number of satisfying die rolls of length $n$ that do not end in $1$.

Let $f(n)$ denote the number of satisfying die rolls of length $n$.

Then:

• $f(n) = f(n,1) + f(n,2).$

• $f(n+1,1) = f(n,2).$
  That is, for any sequence represented by $f(n,2)$,
  you can append a $1$.

• $f(n+1,2) = 5 \times f(n).$
  That is, for any sequence represented by $f(n)$,
  you can append any number other than $1$.

Then, the following table provides the enumeration.

\begin{array}{| r | r | r | r |} \hline n & f(n,1) & f(n,2) & f(n) \\ \hline 1 & 1 & 5 & 6 \\ \hline 2 & 5 & 30 & 35 \\ \hline 3 & 30 & 175 & 205 \\ \hline 4 & 175 & 1025 & 1200 \\ \hline 5 & 1025 & 6000 & 7025 \\ \hline 6 & 6000 & 35125 & 41125 \\ \hline 7 & 35125 & 205625 & 240750 \\ \hline 8 & 205625 & 1203750 & 1409375 \\ \hline 9 & 1203750 & 7046875 & 8250625 \\ \hline 10 & 7046875 & 41253125 & 48300000 \\ \hline \end{array}

See also, lulu's comment, immediately following this answer. I totally overlooked her idea.

---

$\underline{\text{Final Computations}}$

Probability of a sequence of 10 die-rolls, with no consecutive 1's is

$$\frac{48300000}{6^{(10)}} = \frac{503125}{629856}.$$

Probability of at least one occurrence of consecutive $1$'s is

$$1 - \frac{503125}{629856} = \frac{126731}{629856}.$$

Answer 2

Inclusion-exclusion works, you just need to apply it in a clever way.

To fix this overlap problem, we use this clever trick. For each $i\in \{1,\dots,8\}$, let $$ T_i=\{\text{sequences where the $i^\text{th}$ and $(i+1)^\text{st}$ rolls are $1$, but the $(i+2)^\text{nd}$ rolls is not $1$}\} $$ and then define $T_9$ to just be your $S_9$, the set of rolls where dice $9$ and $10$ are both $1$. The point is that $T_i$ works just as well for PIE, because $$ S_1\cup \dots \cup S_9=T_1\cup \dots \cup T_9, $$since if you can find $(1,1)$ somewhere in your sequence, you can also find $(1,1,x)$ for some $x\neq 1$, except in the case where $(1,1)$ occurs at the end.

The size of the intersections then works as follows. Suppose we are counting the $k$-wise intersection $|T_{i(1)} \cap \dots \cap T_{i(k)}|$, for indices $i(1)<i(2)<\dots<i(k)$. If there are any consecutive indices which are at most $2$ apart, i.e. if there exists $j\in \{1,\dots,k-1\}$ such that $$ i(j)\le i(j-1)+2, $$ then we automatically have $|T_{i(1)} \cap \dots \cap T_{i(k)}|=0$. This is because a consecutive subsequence like $(1,1,x)$ (with $x\neq 1)$ at position $i(j-1)$ cannot overlap with a subsequence of $(1,1,x)$ or $(1,1)$ at $i(j)$. This is the benefit of using $T_i$ over $S_i$; many intersections just become zero.

If instead all of the indices are spaced three or more apart, then you can count the size of the intersection in two cases:

• If the greatest index, $i(k)$, is less than $10$, then $|T_{i(1)} \cap \dots \cap T_{i(k)}|=5^{k}\cdot 6^{10-3k}$.

• If instead $i(k)=10$, then $|T_{i(1)} \cap \dots \cap T_{i(k)}|=5^{k-1}\cdot 6^{10-3k+1}$.

Therefore, if we let $$ \begin{align} f(k)&=\text{# size $k$ subsets of $\{1,\dots,9\}$ which are spaced apart by three or more}\\ g(k)&=\text{# size $k$ subsets of $\{1,\dots,9,10\}$ which include $10$}\\ &\;\;\;\;\;\text{ and are spaced apart by three or more}, \end{align} $$ then PIE gives us $$ |T_1\cup \dots \cup T_9|= \sum_{k=1}^9(-1)^k\left[f(k)\cdot 5^{k}\cdot 6^{10-3k}+g(k)\cdot 5^{k-1}\cdot 6^{10-3k+1}\right] $$ All that remains is to compute $f(k)$ and $g(k)$. These are counting problems which are not trivial, but at least much easier then the original question. You can show that $$ f(k)=\binom{9-2(k-1)}{k},\qquad g(k)=\binom{7-2(k-2)}{k-1} $$