2

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

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467
KH Kim
  • 1,121
  • 2
  • 10
  • 25
  • 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 01:04

1 Answers1

1

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

Michael M
  • 10,553
  • 5
  • 27
  • 43