Probability of a contiguous sub-sequence with different elements

Question

Let $a$ and $b$ be two positive integers, and say $b\gg a$. Let $S$ be a random sequence with $ab$ elements, whose entries are all integers from $1$ to $a$, such that each number from $1$ to $a$ appears exactly $b$ times. What is the probability that $S$ contains a consecutive sub-sequence $\{s_i,\dots,s_{i+a-1}\}$, whose elements are all distinct? What if I look for a contiguous sub-sequence of, say $2a$ elements $\{s_i,\dots,s_{i+2a-1}\}$, such that each number $1$ to $a$ appears at least once? This seems like it should be easy, but I am having difficulty with the dependencies.

Answer 1

I don't know if this helps, but we can compute the expected number of such good sequences quite easily.

First: What is the number of good sequences starting at position 1?

Well, the first element can be chosen in $a$ ways, the next $a-1$ and so on, so we get $a!$ such ways.

There are $(ab)!/(b!)^a$ words of length $ab$ in total (permute all letters, but for all instances of $b$ equal letters, we need to compensate). Thus, the expected number of good sequences at position 1 is $$ \frac{a! (b!)^a}{(ab)!}. $$ Now, there is nothing special about the first sequence, so we can just sum the above over all $ab-a+1$ starting positions. Thus, the expected number of good sequences is $$ \frac{a!(ab-a+1) (b!)^a}{(ab)!}. $$