applet-magic.com
*Thayer Watkins* Silicon Valley & Tornado Alley USA |
---|

Let S be a set of events and let p_{x} be the probability of an event x occurring in one
period. The probability of a run of n x's is p_{x}^{n}(1−p_{x}) for n≥1.
(Runs of length zero are excluded because their inclusion would constitute double counting. A run of length
zero for x is simultaneously the beginning of a run of a non-x.)

It must be verified that the set of probabilities p_{x}^{n}(1−p_{x}) constitute
a proper set of probabilities for the set of run lengths; i.e., that they sum to unity.

Σ_{n=1}^{∞}p_{x}^{n}(1−p_{x})
= p_{x}(1-p_{x})Σ_{n=1}^{∞}p_{x}^{n-1}
= p_{x}(1-p_{x})(1/(1-p_{x})) = p_{x}

Therefore the probabilities p_{x}^{n}(1−p_{x}) must be divided by
p_{x} to get a proper set of probilities; i.e., the proper probability of a run of n x's is
p_{x}^{n-1}(1−p_{x}).

The expected run length is then

E{n} = Σ_{n=1}^{∞}np_{x}^{n-1}(1−p_{x})
= (1−p_{x})Σ_{n=1}^{∞}np_{x}^{n-1}

The sum Σ_{n=1}^{∞}np_{x}^{n-1} is equal to 1/(1−p_{x})²
and therefore

E{n} = (1−p_{x})/(1−p_{x})² = 1/(1−p_{x})

The expected length of a run is then

Σ_{x∈S} p_{x}/(1−p_{x})

This formula tends to give dominance to the largest values of p_{x}.

For example, if S={a, b, c} and p_{a}=p_{b}=p_{c}=1/3 then
E{n_{a}}=E{n_{b}}=E{n_{c}}=1/(1-1/3) = 1/(2/3) = 3/2 and
E{n} = 3(1/3)(3/2) = 3/2.

If p_{a}=1/4, p_{b}=1/2 and p_{c}=1/4 then
E{n_{a}}=E{n_{c}=1/(1-1/4)=4/3 and E{n_{b}}=1/(1-1/2) = 2. Thus
E{n} = (1/4)(4/3) + (1/2)(2) + (1/4)(4/3) = (1/3) + 1 + (1/3) = 5/3.

(To be continued.)

**
**