Probability of some die face being missed N or more times in a row in M rolls? [Clarified] 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 

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

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:

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.
 A: 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.
A: 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.
