5
$\begingroup$

2015/01/28 Clarification: Question rewritten to remove ambiguity that elicited (interesting) responses to a different problem (use edit should you wish to view).

From Markus' feedback on the earlier question:

Let's consider a die with $F$ faces. This die is rolled $M$ times. What is the probability, that each window of size $N \leq M$ within this series of $M$ rolls contains always all $F$ faces?

Or alternatively, consider an urn with $F$ differently colored balls, where $M$ balls are drawn (with replacement after each draw) and the colors noted. What is the probability given $F$, $M$, and some $N \leq M$ that every consecutive $N$ draws of the $M$ total draws exhibited at least one example each of all $F$ colors?

Obviously, if $M<N$ or $N<F$ the probability is 0. I'm stuck for the $F\leq N \leq M$ cases.

I can do this using recursive calculation or a Markov chain, but only for the most trivial (small) cases, since the state space obviously explodes quite quickly.

I thought of treating it like a runs/streak problem, that is, I thought that if some face/color is seen, followed by $N$ all of differing face/color resulting in a "failure", I could just use existing means of calculating a streak of $N$ events with probability $(faces - 1)/(faces)$ for the event of a differing face/color. I was unable to arrive at a solution this way.

I then thought of treating it as a coupon collector's problem. I can easily calculate the probability of all faces/colors being seen in the first $N$, so I thought using that, the next "window" from 2 to N+1 is a "failure" if those $N$ are all different from the 1st element (probability $((faces - 1)/(faces))^N$), continuing this for each step of the "window" by 1 to get a net probability. I get stuck here with the dependency between successive "windows", and I'm not even sure if it's a valid tack.

I attempted to find a generating function by looking at actual example counts of differing cases, and searching OEIS for sequences along with checking for generating/sequence functions in Mathematica. I found no matches, and I'm a neophyte with generating functions, so I hit a dead end there.

Bottom line, given $F, M, N$, how might I calculate this?

A couple of examples follow to clarify the above problem description.

Given an alphabet of two elements ${0,1}$, ($F=2$) the possible words of length 4 ($M=4$) are

enter image description here

With a "window" of 3 ($N=3$), the only length 4 words that have no missing alphabet elements in all possible length 3 "windows" are

enter image description here

So, my probability of missing some alphabet element in a 3-windowed 4-length string on a 2-element alphabet is 6/16.

For a more involved example, take the length 6 strings on $0,1,2,3$. There are 4096 of them (I'll not list them for obvious reasons). For a "window" of 5, only 528 of them have the complete alphabet in all possible length 5 consecutive positions. A few examples:

enter image description here

Note that in all of these, positions 1 through 5 and 2 through 6 for each have at least one example of every element in the alphabet.

That number (528 in this example, or equivalently 3568 for the complement) is what I'm after.

I hope that clarifies the question, apologies to readers for any confusion I caused.

2015/01/30 - I've awarded the current bounty to Markus, even though the answer was for a different problem (my fault, my ambiguously written OP), rather than have it vanish into the ether. His response prompted me to look at the problem in other ways and was most interesting in itself. I shall add another bounty if/when it is allowed, and/or award one manually should a solution present itself.

$\endgroup$
  • $\begingroup$ When you say "some" do you mean a given face (say $5$) was not seen for $N$ or more consecutive rolls, or do you mean there are $N$ or more consecutive rolls in which not all faces come up? For example, both $1,2,3,5,6,6$ and $1,1,3,4,5,6$ do not satisfy the former as $5$ appears, but both satisfy the latter as neither contain all the faces $1$-$6$ (for $F=6$). $\endgroup$ – Ari Jan 2 '15 at 9:09
  • $\begingroup$ @Ari I think he means the probability of a particular face not appearing for $N$ times in a row, when rolled $M$ times. (which basically means $1$ minus the probability of a face repeating $N$ times in a row, in $M$ rolls) $\endgroup$ – ghosts_in_the_code Jan 2 '15 at 9:15
  • $\begingroup$ @HammyTheGreek I know for sure it is approachable, even for an unfair dice, but I don't known exactly what the formula is. $\endgroup$ – ghosts_in_the_code Jan 2 '15 at 9:17
  • $\begingroup$ @ari: I edited the question to clarify - and your "N or more consecutive rolls in which not all faces come up" is what I meant. $\endgroup$ – HammyTheGreek Jan 2 '15 at 9:27
  • $\begingroup$ I suspect either your calculations (second paragraph) or your program are wrong. You have not shown either, so we cannot find the error. $\endgroup$ – Ross Millikan Jan 5 '15 at 5:44
3
+100
$\begingroup$

Attention: [2015-01-28] According to a reformulation of OPs question clarifying ambiguous aspects, this answer is no longer valid. It instead adresses the problem stated a few paras below. Nevertheless, since the elaboration might be useful for the interested reader, I will not remove it.


Note: The following is a two-step approach. I will start with a simpler problem in order to be well prepared for the more challenging problem stated by OP. We also take a look at small examples as simple plausability check. We will see that the resulting generating function is the one stated by @RusMay.


The following is based upon section I.4.1 and example III.24 from Analytic Combinatorics by P. Flajolet and R.Sedgewick.

Let's denote the $F$ faces with $a_1,\ldots,a_F$. Each result from $M$ rolls can be seen as word of length $M$ consisting of characters from the alphabet $\mathcal{A}=\{a_1,\ldots,a_F\}$.We can reformulate OPs question and get following

Problem: Let's use an alphabet $\mathcal{A}=\{a_1,\ldots,a_F\}$ of $F$ characters. What is the number $C_F(M,N)$ of different words of length $M$ with longest runs of a character having length less than $N(\geq 2)$.

The corresponding probability OP is asking for is the number $C_F(M,N)$ divided by the number $F^M$ of all words of length $M$ over the alphabet $\mathcal{A}$.

First Step: Analysing the case $F=2,N\geq 2$

We consider binary strings over the alphabet

\begin{align*} \mathcal{A}=\{0,1\} \end{align*}

and are looking for the number of strings of length $M$ having less than $N$ consecutive $0$s and $1$s.

We build the binary strings starting with simpler patterns. Let $$\text{SEQ}(1)=\{\varepsilon,1,11,111,\ldots\}$$ denote all strings containing only $1$s with length $\geq0$. The empty string is denoted with $\varepsilon$. The corresponding generating function is $$z^0+z^1+z^2+\ldots=\frac{1}{1-z},$$ with the exponent of $z^n$ marking the length $n$ of a string of $1$s and the coefficient of $z^n$ marking the number of strings of length $n$. Similarly, we define $\text{SEQ}(0)=\{\varepsilon,0,00,000,\ldots\}$.

Let $\text{SEQ}^{\leq k}(1)$ be the set of all strings of $1$s with length $\leq k$. The generating function for $\text{SEQ}^{\leq k}(1)$ is $$1+z+z^2+\ldots+z^{k}=\frac{1-z^{k+1}}{1-z}$$

Even more simplified: We consider $$F=2, N=2$$ namely strings having runs of $0$s and $1$s with maximum length $1$.

How could we describe all these strings? We may have a leading $1$. So, we start with zero or one $1$s. Formally: \begin{align*} \text{SEQ}^{\leq 1}(1)=\{\varepsilon,1\} \end{align*} with generating function \begin{align*} 1+z\tag{1} \end{align*}

Then we may have zero or more groups, each group containing a $0$ followed by a $1$. Formally:

$$\text{SEQ}(01)=\{\varepsilon,01,0101,010101,\ldots\}$$

with generating function

\begin{align*} 1+z^2+z^4\ldots=\frac{1}{1-z^2}\tag{2} \end{align*} The strings may finish with zero or one $0$, formally $\text{SEQ}^{\leq 1}(0)$ with generating function $1+z$.

We conclude: The binary strings having runs of $0$s and $1$s of maximum length $1$ are modelled by

\begin{align*} \text{SEQ}^{\leq 1}(1)\text{SEQ}(01)\text{SEQ}^{\leq 1}(0)\tag{3} \end{align*}

with generating function \begin{align*} \left(1+z\right)\left(\frac{1}{1-z^2}\right)\left(1+z\right)=\frac{1+z}{1-z} \end{align*}

according to (1) and (2)


Generalisation: $F=2,N\geq 2$

We consider now the more general problem $N\geq 2$. Since we have to consider runs of less than $N$ $0$s and $1s$ we have to substitute the outer occurrences $0$ and $1$ by up to $N-1$ $0$s resp. $1$s and the inner $0$s and $1$s enlarge by up to $N-2$ $0$s resp. $1$s. We obtain

\begin{align*} \text{SEQ}^{\leq N-1}(1)\text{SEQ}\left(0\text{SEQ}^{\leq N-2}(0)1\text{SEQ}^{\leq N-2}(1)\right)\text{SEQ}^{\leq N-1}(0) \end{align*}

with corresponding generating function $A(z)$

\begin{align*} A(z)&=\left(\frac{1-z^N}{1-z}\right)\left(\frac{1}{1-z\frac{1-z^{N-1}}{1-z}z\frac{1-z^{N-1}}{1-z}}\right)\left(\frac{1-z^N}{1-z}\right)\\ &=\frac{(1-z^N)^2}{(1-z)^2-z^2(1-z^{N-1})^2}\\ &=\frac{1-z^N}{1-2z+z^N}\tag{4} \end{align*}

Note: Observe, that (4) corresponds to the generating function given by @RusMay with $F=2$


Example: $F=2, N=3$

The generating function counting the number of binary strings with consecutive runs of length less than 3 is

\begin{align*} \frac{1-z^3}{1-2z+z^3}=1+2z+4z^2+6z^3+10z^4+\ldots \end{align*}

the corresponding strings are

\begin{align*} \{&\varepsilon,\\ &0,1,\\ &00,01,10,11,\\ &001,010,011,100,101,110,\\ &0010,0011,0100,0101,0110,1001,1010,1011,1100,1101,\\ &\ldots\} \end{align*}

This was the warm-up exercise and we are now well-prepared for the general solution.


Second Step: General solution $F\geq 2,N\geq 2$

Words with consecutive runs having length exactly one are called Smirnov words. Observe, in (3) we described Smirnov words over a binary alphabet with the generating function $\frac{1+z}{1-z}$.

Let $\mathcal{W}=SEQ(\mathcal{A})$ be the set of words over the alphabet $\mathcal{A}=\{a_1,\ldots,a_F\}$, and $\mathcal{S}$ be the set of Smirnov words. We need two observations:

  • Aspect 1: The generating function $W(v_1,\ldots,v_F)$ counting the number of words of $\mathcal{W}$ with $v_j$ denoting the number of occurrences of the letter $a_j$, $1 \leq j \leq F$ is

\begin{align*} W(v_1,\ldots,v_F)=\frac{1}{1-(v_1+\ldots+v_F)}\tag{5} \end{align*}

Note: Here I follow Flajolet's advice and omit the redundant variable $z$ in $W$ which is otherwise used to mark the length of the words. This job is already done by $v_1,\ldots,v_F$ and so I don't need to use $W(z;v_1,\ldots,v_F)=\frac{1}{1-(v_1+\ldots+v_F)z}$ instead.

  • Aspect 2: We can take an arbitrary word from $\mathcal{W}$ and substitute each run of characters by only one occurrence of this character in order to get a Smirnov word. On the other hand, we can find to each word $w\in \mathcal{W}$ a Smirnov word $s_w\in\mathcal{S}$ and expand each character of $s_w$ by a proper run length of this character in order to get the corresponding word $w\in \mathcal{W}$.

So, arbitrary words in $\mathcal{W}$ are derived from Smirnov words by a simultaneous substitution:

\begin{align*} \mathcal{W}=\mathcal{S}[a_1\mapsto SEQ^{\geq 1}(a_1),\ldots,a_F\mapsto SEQ^{\geq 1}(a_F)]\tag{6} \end{align*}

Let $S(v_1,\ldots,v_F)$ denote the generating function counting the number of Smirnow words in $\mathcal{S}$.

The substitution in (6) implies the relation:

\begin{align*} W(v_1,\ldots,v_F)=S\left(\frac{v_1}{1-v_1},\ldots,\frac{v_F}{1-v_F}\right)\tag{7} \end{align*} since similarly to (2) the generating function for \begin{align*} SEQ^{\geq 1}(a_j)=\{a_j,a_ja_j,a_ja_ja_j,\ldots\} \end{align*} is $$\frac{v_j}{1-v_j}$$

We observe $S(v_1,\ldots,v_F)$ is specified in (7) implicitely by $W(v_1,\ldots,v_F)$. Since the inverse function of $\frac{v}{1-v}$ is $\frac{v}{1+v}$ we obtain with the help of (5):

\begin{align*} S(v_1,\ldots,v_F)&=W\left(\frac{v_1}{1+v_1},\ldots,\frac{v_F}{1+v_F}\right)\\ &=\left(1-\sum_{j=1}^{F}\frac{v_j}{1+v_j}\right)^{-1} \end{align*}

We can proceed even simpler, since we don't need to differentiate between the characters of the alphabet $\mathcal{A}$. So, if we set $v_j=z$ and so forget the composition of the words into letters, we obtain the generating function for Smirnov words

\begin{align*} \frac{1}{1-F\frac{z}{1+z}}&=\frac{1+z}{1-(F-1)z}\tag{8}\\ &=1+\sum_{n=1}^{\infty}F(F-1)^{n-1}z^n \end{align*}

From here it's only a small step to find the generating function of words, that never contain runs of $N$ consecutive equal letters. We follow aspect 2 and substitute each character by a run of length less than $N$. In terms of generating functions we have to substitute in (8)

$$z\mapsto z\frac{1-z^{N-1}}{1-z}.$$

We finally obtain the

Solution: The generating function $\tilde{S}(z)$ counting all words over the alphabet $\mathcal{A}=\{a_1,\ldots,a_F\}$ with runs of length less than $N$ consecutive characters is

\begin{align*} \tilde{S}(z)=\frac{1}{1-F\frac{z\frac{1-z^{N-1}}{1-z}}{1+z\frac{1-z^{N-1}}{1-z}}}=\frac{1-z^{N}}{1-Fz+(F-1)z^{N}} \end{align*}

If $C_F(M,N)$ denotes the coefficient of $[z^M]\tilde{S}(z)$ the wanted probability is $$\frac{C_F(M,N)}{F^M}$$

Note: Observe that $\tilde{S}(z)$ is the generating function also given by @RusMay.


Let's finish with two small examples:

Example: $F=3,N=3,\mathcal{A}=\{0,1,2\}$

The generating function counting the number of ternary strings with consecutive runs of length less than 3 is

\begin{align*} \frac{1-z^3}{1-3z+2z^3}=1+3z+9z^2+24z^3+66z^4+\ldots \end{align*}

the corresponding strings are

\begin{align*} \{&\varepsilon,\\ &0,1,2\\ &00,01,02,10,11,12,20,21,22\\ &001,002,010,011,012,020,021,022,\\ &100,101,102,110,112,120,121,122,\\ &200,201,202,210,211,212,220,221,\\ &0010,0011,0012,0020,0021,0022,0100,0101,0102,0110,0112,\\ &0120,0121,0122,0200,0201,0202,0210,0211,0212,0220,0221,\\ &1001,1002,1010,1011,1012,1020,1021,1022,1100,1101,1102,\\ &1120,1121,1122,1200,1201,1202,1210,1211,1212,1220,1221,\\ &2001,2002,2010,2011,2012,2020,2021,2022,2100,2101,2102,\\ &2110,2112,2120,2121,2122,2200,2201,2202,2210,2211,2212,\\ &\ldots\} \end{align*}

Example: $F=3,N=4,\mathcal{A}=\{0,1,2\}$

The generating function counting the number of ternary strings with consecutive runs of length less than 4 is

\begin{align*} \frac{1-z^4}{1-3z+2z^4}=1+3z+9z^2+27z^3+78z^4+\ldots \end{align*}

the corresponding strings are

\begin{align*} \{&\varepsilon,\\ &0,1,2\\ &00,01,02,10,11,12,20,21,22\\ &000,001,002,010,011,012,020,021,022,\\ &100,101,102,110,111,112,120,121,122,\\ &200,201,202,210,211,212,220,221,222,\\ &0001,0002,0010,0011,0012,0020,0021,0022,0100,\\ &0101,0102,0110,0111,0112,0120,0121,0122,0200,\\ &0201,0202,0210,0211,0212,0220,0221,0222,1000,\\ &1001,1002,1010,1011,1012,1020,1021,1022,1100,\\ &1101,1102,1110,1112,1120,1121,1122,1200,\\ &1201,1202,1210,1211,1212,1220,1221,1222,2000,\\ &2001,2002,2010,2011,2012,2020,2021,2022,2100,\\ &2101,2102,2110,2111,2112,2120,2121,2122,2200,\\ &2201,2202,2210,2211,2212,2220,2221,\\ &\ldots\} \end{align*}


Note: According to P. Flajolet (p.205) this example applies equally well to non-uniform letter probabilities and to a collection of run-length upper-bounds and lower-bounds dependent on each particular letter. This topic is in particular pursued by different methods in several works of S. Karlin and coauthors.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the detailed answer. I'm still not clear how this answers it - perhaps I'm just being incredibly dense: Yes, this counts strings from an alphabet with some specified run limit, but how does that answer how many strings of some length have no sequence of consecutive elements of some length >= length of alphabet and <=length of string that are not missing any of the alphabet? Also, is there a typo in your example? There's an example string with a run of three, and I get $\frac{1-z^3}{2 z^3-3 z+1}$ for the G.F. I'll continue to try understand this example. Thanks again, really!. $\endgroup$ – HammyTheGreek Jan 27 '15 at 19:51
  • $\begingroup$ I've added an example to be sure that we're on the same page. Again, thanks for the answer, I'm going through it step-by-step to understand it and ensure I'm not just a dope here. $\endgroup$ – HammyTheGreek Jan 27 '15 at 20:16
  • $\begingroup$ @HammyTheGreek: Hi and thanks for your hint. I've corrected my example. Now the coefficient of $z^3$ is $24$ and there are actually $24$ strings each having length $3$ with runs of maximum length $2$. :-) And don't worry, this example is not simple. It takes some time to become familiar with these concepts. $\endgroup$ – Markus Scheuer Jan 27 '15 at 20:22
  • $\begingroup$ @HammyTheGreek: Regarding to your question: The clou is, to first do some kind of normalisation by considering Smirnov words only. This way we have only runs of length $1$ and the situation is better manageable. Then we expand the words by enlarging characters by sequences of exactly this character of length $1$ up to $N-1$. This is realised by the transformation $z \mapsto z\frac{1-z^{N-1}}{1-z}$ $\endgroup$ – Markus Scheuer Jan 27 '15 at 20:27
  • $\begingroup$ Would you be so kind if you have the time to do an example with alphabet of 3 elements, length 4 strings, window of 3? I'm working through the answer and generating test cases in Mathematica, and for this simple case, I get an expansion of the G.F. (f=3, n=4) of $1+3 z+ 9 z^2 + 27 z^3 + 78 z^4 ...$. But there are 81 words, 75 which miss having all three alphabet elements in all possible length 3 consecutive positions. Perhaps an example of that might help me wrap my head around this - I'd love to award you & rus both (and will), though I fear I'm not qualified to judge correctness here ;-( $\endgroup$ – HammyTheGreek Jan 27 '15 at 22:01
2
$\begingroup$

The "easy" way to enumerate strings of a particular length that avoid any collection of words is the so-called Goulden-Jackson cluster method. This method is elegantly described in a wonderful paper by Zeilberger and Noonan. (This paper is intended as a gentle introduction to the Goulden-Jackson cluster method and has almost no prerequisites.) In it they concretely describe how to easily obtain the generating function for words of various lengths that avoid a collection of "bad words". In your case, say $a_M$ is the number of rolls of length $M$ that avoid all the bad words of the form $i^N$ for $1\le i\le F$. Their method shows that the corresponding generating function $\sum_{M\ge0}a_M z^M$ is $$\frac{1-z^N}{1-Fz+(F-1)z^{N}}.$$ Of course, there's still the problem of extracting the coefficient of $z^M$ from this rational function, but perhaps this is enough to get you started.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I shall grab the reference presently, and see if I can wrap my head around this. Thank you. $\endgroup$ – HammyTheGreek Jan 6 '15 at 1:22
  • $\begingroup$ First try reading the reference - a bit above my pay grade, but I'll have at it. I tried plugging your G.F. into Mathematica & comparing coefficients of the expansion to some example tuples, hoping that might light the bulb, but the results make no sense to me: E.g., using Series in Mathematica to expand the G.F. after setting f=2 and n=2 (to visually compare coefficients to all 2-tuples of {1,2}), I don't even get a result with an exponent of 2 (for a length 2 roll on two faces). Am I completely misunderstanding how to use the G.F.? I'd expect the coeff. to be 2 (for good {1,2} and {2,1}). $\endgroup$ – HammyTheGreek Jan 6 '15 at 6:02
  • $\begingroup$ Rus - just read my comment, it could be read as imploring you to first try reading the reference - not what I meant - it was my first attempt at understanding it. Sorry if it came off the wrong way. $\endgroup$ – HammyTheGreek Jan 7 '15 at 19:14
  • $\begingroup$ Apologies here---I misstated the generating function. The $z^{N-1}$ term in the denominator should have been $z^N$. With that correction, the generating function for the case where $f=2$ and $n=2$ is $\frac{1+z}{1-z}=1+2z+2z^2+2z^3+\cdots$, as expected. By the way, no matter what your level is, that paper is really worth reading. (I consider it a golden nugget in combinatorics.) $\endgroup$ – Rus May Jan 8 '15 at 1:07
  • $\begingroup$ I'd actually already tried that ;-), then the results for other cases make no sense (no coeffs. match counts of small enumerated test cases). Finished 1st read of ref. (thanks, interesting!), it is a bit beyond my dilettante level but expect a few more reads it will sink in. Nonetheless, not sure it's applicable - seems I'd need to provide a list of "bad" words (blanks extension won't work), and that alone explodes exponentially. I gen'd some tuple/count data, sent to superseeker at OEIS, zero hits. This is turning out to be a most interesting puzzle. $\endgroup$ – HammyTheGreek Jan 8 '15 at 6:42
0
$\begingroup$

If the numbers involved are small, you just have to compute them. If $F$ is large, the chance of two in a row on a given pair is $1/F^2$ and the chance of a pair (because the first can be anything) is $1/F$ You can use a Poisson distribution here. You haven't specified the calculation well enough to do it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the response. I don't know how to calculate this is the problem I'm having (well, I know how to with a Markov chain or using a recursive algorithm, but neither scales beyond trivial sizes for obvious reasons). I had initially thought "This is just a streak problem in reverse", i.e., asking the p of a streak of non-successes (where the (f-1)/f comes from), but I realized that is flawed, since that accounts only for a streak of faces that are not a specific face between two occurrences of that specific face. So, I am hoping there's some method I've not seen. Thanks again. $\endgroup$ – HammyTheGreek Jan 5 '15 at 5:55
  • $\begingroup$ Naively, the chance of a run of $n$ starting at a given point is $F^{(n-1)}$. For $M$ rolls, you have $M-n+1$ chances. If the chance is small, it is $(M-n+1)F^{n-1}$ $\endgroup$ – Ross Millikan Jan 5 '15 at 6:03
  • $\begingroup$ yep, already using that as an estimator, along with just simulating. Looking for a tractable exact solution, if one exists. Really appreciate the response - I've pondered this and searched the literature for similar to the point of a headache... $\endgroup$ – HammyTheGreek Jan 5 '15 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.