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

  • $\begingroup$ 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? $\endgroup$ – whuber Aug 11 '14 at 17:13
  • $\begingroup$ 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$. :) $\endgroup$ – KH Kim Aug 12 '14 at 1:04

This is an old question, see e.g. this article for answering different aspects of the problem.

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).

  • $\begingroup$ nice reference! $\endgroup$ – jpmuc Aug 11 '14 at 15:14
  • $\begingroup$ Indeed. Sad that most relevant (and also irrelevant) combinatorics questions are already answered ;) $\endgroup$ – Michael M Aug 11 '14 at 15:18
  • 2
    $\begingroup$ The main difference is that my question concerns the multinomial case. Thanks for good reference anyway! $\endgroup$ – KH Kim Aug 12 '14 at 1:08
  • $\begingroup$ (+1) good point. $\endgroup$ – Michael M Aug 12 '14 at 18:13

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.