Has anyone invented a computationally simple method to calculate the probability of at least n1-consecutive die rolls, for n2-sided die, n3-rolls?

Question

I think I have invented a formula that allows a computer to very easily calculate the probability of at least n1-consecutive die rolls, on an n2-sided die, rolling it n3-times.

For example, for a 3-sided die being rolled 4 times, the probability of at least 3 consecutive rolls being the same is: $$\frac{5}{27} \sim 0.185185$$

A 10-sided die being rolled 20 times with at least 4 consecutive rolls: $$\frac{153252438815221561}{10000000000000000000} \sim 0.0153252$$

A 20-sided die being rolled 100 times with at least 5 consecutive rolls: $$\frac{36138486362801675395834082841530471263391618236217471764311872542282160082804618163213 4714483039586709049484138205953646876021}{63382530011411470074835160268800000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000} \sim 0.000570165$$

A 150-sided die being rolled 250 times with at least 10 consecutive rolls: $$\frac{43754862099840059340989164536890668843600275210242353790609200399332108157129005621344 12966072844123998821529817954285993344643635690087672932957210052124849484632371945364241 27895214917314522967829996314996884843354909465711479333655125328467972639354192054002381 80358736161798175079981214320161396998878382245814510025222948918658240716181935621089269 06271521762936897812401688121481273594338138312959838934408957524646299446591373165468391 26633170992252043228387167654509762247790434963321680468677569650750302475087706401}{7026 24848833633473725832814569816725466578833488064526319504046334823913293570611014402352480 20759777065059629450925139424048788112889589987529495486017499085597652471999291372698929 85667366792663663798677273390781336908763915319543616880317198383190582106072596957346831 91403746604919433593750000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000} \sim \text{6.2273433927754916$\grave{ }$*${}^{\wedge}$-18}$$

What I want to know, is there a method out there that already exists which is finding what I am already able to find? I am really scared that I have wasted my time 'inventing' something that someone has already done before as my literature review has come up empty. I am also a bit weary to share my method at the moment because I would ideally want to write a paper on this if this has not been done before.

Edit: You can generate tables with this easily too. For a 6-sided die for up to 15-rolls and -consecutive: $$ \left( \begin{array}{ccccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{1}{6} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{11}{36} & \frac{1}{36} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{91}{216} & \frac{11}{216} & \frac{1}{216} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{671}{1296} & \frac{2}{27} & \frac{11}{1296} & \frac{1}{1296} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{4651}{7776} & \frac{751}{7776} & \frac{1}{81} & \frac{11}{7776} & \frac{1}{7776} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{31031}{46656} & \frac{5531}{46656} & \frac{7}{432} & \frac{1}{486} & \frac{11}{46656} & \frac{1}{46656} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{201811}{279936} & \frac{2177}{15552} & \frac{5611}{279936} & \frac{7}{2592} & \frac{1}{2916} & \frac{11}{279936} & \frac{1}{279936} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{1288991}{1679616} & \frac{270241}{1679616} & \frac{40091}{1679616} & \frac{13}{3888} & \frac{7}{15552} & \frac{1}{17496} & \frac{11}{1679616} & \frac{1}{1679616} & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{8124571}{10077696} & \frac{1827071}{10077696} & \frac{15497}{559872} & \frac{40171}{10077696} & \frac{13}{23328} & \frac{7}{93312} & \frac{1}{104976} & \frac{11}{10077696} & \frac{1}{10077696} & 0 & 0 & 0 & 0 & 0 \\ 1 & \frac{50700551}{60466176} & \frac{126731}{629856} & \frac{979}{31104} & \frac{279851}{60466176} & \frac{31}{46656} & \frac{13}{139968} & \frac{7}{559872} & \frac{1}{629856} & \frac{11}{60466176} & \frac{1}{60466176} & 0 & 0 & 0 & 0 \\ 1 & \frac{313968931}{362797056} & \frac{80043931}{362797056} & \frac{12790681}{362797056} & \frac{106217}{20155392} & \frac{279931}{362797056} & \frac{31}{279936} & \frac{13}{839808} & \frac{7}{3359232} & \frac{1}{3779136} & \frac{11}{362797056} & \frac{1}{362797056} & 0 & 0 & 0 \\ 1 & \frac{1932641711}{2176782336} & \frac{521516711}{2176782336} & \frac{84941711}{2176782336} & \frac{6619}{1119744} & \frac{1912811}{2176782336} & \frac{1}{7776} & \frac{31}{1679616} & \frac{13}{5038848} & \frac{7}{20155392} & \frac{1}{22674816} & \frac{11}{2176782336} & \frac{1}{2176782336} & 0 & 0 \\ 1 & \frac{11839990891}{13060694016} & \frac{561766711}{2176782336} & \frac{11638417}{272097792} & \frac{24761}{3779136} & \frac{715337}{725594112} & \frac{1912891}{13060694016} & \frac{1}{46656} & \frac{31}{10077696} & \frac{13}{30233088} & \frac{7}{120932352} & \frac{1}{136048896} & \frac{11}{13060694016} & \frac{1}{13060694016} & 0 \\ 1 & \frac{72260648471}{78364164096} & \frac{21637367221}{78364164096} & \frac{50620543}{1088391168} & \frac{563631721}{78364164096} & \frac{44059}{40310784} & \frac{12876971}{78364164096} & \frac{41}{1679616} & \frac{1}{279936} & \frac{31}{60466176} & \frac{13}{181398528} & \frac{7}{725594112} & \frac{1}{816293376} & \frac{11}{78364164096} & \frac{1}{78364164096} \\ \end{array} \right) $$

Answer 1

You can get a recursive formula: For simplicity treat a 6-sided die. Fix $k\geq 1$ and look for $k$ or more consecutive rolls of the same number in $n$ total rolls (where $n\geq k$). Then if $P(n)$ is the success probability we get: \begin{align} P(k)&=6(1/6)^k\\ P(n+1)&=P(n)+ 5(1/6)^k(1-P(n-k+1)) \quad \forall n \geq k \end{align}

---

This can be derived as follows for a given $n\geq k$: $$P(n+1) = P[\mbox{success in first $n$ rolls}] + \sum_{i=1}^6 P[A_i] $$ where for $i\in \{1, ..., 6\}$, $A_i$ is defined as the event that there is no success in the first $n$ rolls, but the rolls $\{n-k+2,...,n+1\}$ are all $i$ (that is, the last $k$ rolls of our total $(n+1)$ rolls are all $i$). Of course $P[A_i]$ is the same for all $i \in \{1, ..., 6\}$ so it suffices to compute $P[A_1]$. Then $A_1$ is the event that we get $1$ on the rolls $\{n-k+2, ..., n+1\}$ and that we do not get a success in the first $n-k+1$ rolls and the roll $(n-k+1)$ is a number in the set $\{2, ..., 6\}$.
That is $$P[A_1] = \underbrace{(5/6)(1-P(n-k+1))}_{\mbox{for rolls $\{1, ..., n-k+1\}$}}(1/6)^k$$

---

You can turn this into an integer-based formula to match your table results by defining: $$ Q(n) = 6^nP(n)$$ Then \begin{align} Q(k) &= 6\\ Q(n+1) &= 6Q(n) + 5(6^{n-k+1} - Q(n-k+1)) \quad \forall n \geq k \end{align} and this indeed matches your table results (at least, I spot checked it for the 4th column): For $k=4$ we get your same column-4 values:
\begin{align} Q(4)&= 6 \implies P(4) = \frac{6}{6^4} = \frac{1}{216} \\ Q(5) &= 66 \implies P(5) = \frac{66}{6^5} = \frac{11}{1296}\\ Q(6) &= 576 \implies P(6) = \frac{576}{6^6}= \frac{1}{81}\\ Q(7) &= 4536 \implies P(7) = \frac{4536}{6^7} = \frac{7}{432}\\ Q(8) &=33666 \implies P(8) = \frac{33666}{6^8}= \frac{5611}{279936}\\ Q(9) &=240546 \implies P(9) = \frac{240546}{6^9} = \frac{40091}{1679616}\\ Q(10) &= 1673676 \implies P(10) = \frac{1673676}{6^{10}} = \frac{15497}{559872}\\ Q(11) &= 11419056\implies P(11) = \frac{11419056}{6^{11}}= \frac{979}{31104} \end{align}

Answer 2

As an actual research result, this isn't particularly interesting - there are many easy techniques that would be able to generate the result (recurrence relations, dynamic programming, etc). It ends up being a straightforward exercise.

The problem itself is not particularly difficult and therefore anyone who needs the result would generally be able to just derive it on the spot (as a calculation). On the other hand, it's not fundamental enough that people want the solution (to how to compute it) easily accessible all the time. Hence the lack of publication of this.

[Edit] If what you have is a semi-closed (closed) form, this would be a (really) good article for a combinatorics journal. If it's purely an algorithm that would generate it, that's not enough. If you write it well enough and sell the pedagogy/beauty of the derivation, this might still work for a recreational mathematics publication.

Answer 3

Your problem is equivalent to counting the number of words in $\{1,\ldots,n_2\}^{n_3}$ with subword of length $n_1$ of the form $k^{n_1}$, $k\in\{1,\ldots,n_2\}$. This, in turn, is equivalent to studying the complementary set, i.e. the words in $\{1,\ldots,n_2\}^{n_3}$ which do not contain a subword of the form $k^{n_1}$. Let's call this second set $A$. The cardinality of $A$ is $$\sum_{m=1}^\infty n_2(n_2-1)^{m-1}F(n_1,n_3-1,m),$$ where $F(a,b,c)$ is the number of compositions of $a$ into $c$ parts such that no part is of size $>b$, and $n_2(n_2-1)^{m-1}$ is the number of elements of $\{1,\ldots,n_2\}$ where no number appears twice in a row. Indeed, for such a composition $(\lambda_1,\ldots,\lambda_m)$ and such a tuple $(k_1,\ldots,k_m)$, the word $k_1^{\lambda_1}\cdots k_m^{\lambda_m}$ is in $A$.

The study of $F(a,b,c)$ is done in this MathOverflow question, which tells us that $\#A$ is the coefficient in front of $x^{n_1}$ of the power series $$\sum_{m=1}^\infty n_2(n_2-1)^{m-1}x^m(1-x^{n-3})^m(1-x)^{-m}.$$ There's also a simpler study of integer compositions in this MSE question. I also found an article about integer compositions with bounded size. Of course, none of this gives an explicit expression of $\#A$, but I just wanted to show how your problem fits in with problems that has already been looked at.