2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)!}. $$

$\endgroup$
  • $\begingroup$ Nice but does it work for $ a=b=2$? $\endgroup$ – Bjørn Kjos-Hanssen Oct 9 '14 at 3:55
  • 1
    $\begingroup$ Checking the calculations above is left as an exercise to the reader: it was late yesterday. $\endgroup$ – Per Alexandersson Oct 9 '14 at 5:52

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.