# Distribution of (maximum) run length

I am curious about the distribution of (maximum) run length given

k independent trials when $p(X=1)=p_1, p(X=2)=p_2, ..., p(X=n)=p_n.$

For example, for a coin tossing for 3 independent trials,
$p(X="H")=1/2, p(X="T")=1/2.$

$p(mrl=3)=2*(1/2)^3 for HHH, TTT$

$p(mrl=2)=4*(1/2)^3 for HTT, THH, HHT, TTH$

$p(mrl=1)=1-p(mrl=3)-p(mrl=2)$

But what if for general n and k?

My guess would be $E(mrl)=log_k n$ for uniform distribution

• A general formula will be hard to come by and impossible to write down unless you make some quantitative assumptions about how the $p_n$ vary with $n$. Did you perhaps intend that the $p_n$ be constant, as suggested in the example? – whuber Aug 11 '14 at 17:13
• My ultimate goal is to get the result for general $p_n$. But if it's impossible or nearly impossible, I will be satisfied if I could knew what would happen when $p_i=1/n for 1<=i<=n$. :) – KH Kim Aug 12 '14 at 1:04

It contains a recursive formula for the cumulative distribution function $F_n$ of the longest run for both biased and unbiased coins as well as nice approximate results for the average and variance of this distribution. Logarithms play a central role in these approximations. For instance, the expected length in the unbiased coin case is around $\log_2(n) - 1$ (see page 201).