Runs of the same type within a deck of cards - distribution of runs of different length

Question

My background is in physics, not statistics, so forgive any suspect terminology or notation, but I hope the problem is clearly set out below. Secondly, my statistics is not good enough to recognize whether this problem has been asked elsewhere on the site, so please bear with me.

Suppose we have N objects. A fixed proportion 'p' are of type A, and a proportion 'q' are of type B and these are distinguishable. Objects are either A or B, but not both, so the classes are mutually exclusive.

Objects can not be any other type, and p + q = 1.
Both p and q are non-zero and less than one.

The objects are randomised by some agreed method so that they form a sequence of N objects. This might be equivalent to shuffling a deck of cards, of which a proportion p are Red and a proportion q are black.

A run of length 'c' is defined as a sequence of 'c' objects of one particular type, bounded by either objects of the different type OR the two boundaries of the sequence. For example a run of two A's could be a run of two A's bounded by B's. Or if the sequence starts AAB…., then the first two objects constitute a run of size 2.

Let ' n(c) ' be the number of runs of size 'c', within the collection.

Question: What is the probability distribution of n(c) in a randomized collection of objects?

In other words (if I have understood this correctly), what are the probabilities of such a deck having 0, 1, 2, 3, etc. runs of each possible size, c?

From this, what are...

1. the expected value of n(c)
2. the variance of n(c)

I have seen reference to runs within coin tosses, but I think this problem is different, in that the total proportion of each type of outcome is fixed here, whereas it is not when tossing a coin. I have also noted the other answers on runs within a deck, but these consider runs in general, of any length, rather than the distribution of runs of different lengths.

Answer 1

Let $I_i^c$ be an indicator variable such that:

$$ I_i^c = \begin{cases} 1 & \text{run of length $c$ starts at $i^{th}$ position}, \\ 0 & \text{otherwise} \end{cases} $$

To find $\mathbb{E}[R_c]$ where $R_c$ represents a run of length $c$ we simply make use of this identity(For a run to be of length $c$ it must start at or before $({n-c+1})^{th}$ position: $$ R_c = \sum_{i=1}^{i=n-c+1} I_i $$ Thus, $$ \mathbb{E}[R_c] = \mathbb{E}[\sum_{i=1}^{i=n-c+1}I_i] = \sum_{i=1}^{i=n-c+1} \mathbb{P}(I_i^c=1) $$

Now, consider the event $I_i^c=1$. When $i=1$, the run starts at position 1. It can be $\underbrace{AAAAA\dots}_\text{c times}B $ or $\underbrace{BBBBB\dots}_\text{c times}A $ and hence, the probability is given by: $$ \mathbb{P}(I_1^c=1) = p^c\times q + q^c\times p $$

Similarly, for $i=n-c+1$, $$ \mathbb{P}(I_{n-c+1}^c=1) = p^c\times q + q^c\times p $$

And, for $2 \leq i \leq n-c$,

$$ \mathbb{P}(I_i^c=1) = q\times p^c \times q + p \times q^c \times p $$

And hence, $$ \mathbb{E}[R_c] = (n-c-1)\times(p^cq^2+q^cp^2) +2(p^cq+q^cp) $$

To calculate $\text{Var}[R_c]$ make use of $\text{Var}[R_c] = \mathbb{E}[R_c^2]-(\mathbb{E}[R_c])^2$

Details of variance calculation for runs in flips of coin(which comes close to this problem as you already mentioned) are here