Timeline for Runs in coin flips

6 events

when toggle format	what		by	license	comment
Apr 30, 2014 at 15:59	comment	added	Bjørn Kjos-Hanssen		Oh right it was the number of runs not the length of the longest run
Apr 30, 2014 at 15:00	comment	added	Ben Barber		The second step is to decide whether the value we are concentrated near is 0 or something larger than 1. This is always problem dependent: in this case the expected number of runs of length $k$ is around $n2^{-k}$, so the threshold will be around $\log_2 n$. But to be completely explicit, this isn't the value that we wanted to be reasonably large.
Apr 30, 2014 at 14:59	comment	added	Ben Barber		@BjørnKjos-Hanssen, there are two steps, and we're interested in the mean/median of a different quantity at each stage. At the first stage we ask how many runs of length $k$ there are. Provided the median of this random variable is large, it will be tightly concentrated. ("Large" here just means large enough to make the exponential bounds decay to zero, so larger than $k$ or $k^3$.) In this case the median is linear in $n$, so if $k$ is growing slower than this we will get concentration.
Apr 30, 2014 at 14:18	comment	added	Bjørn Kjos-Hanssen		Nice explanation. Regarding this: "provided the median grows at some reasonable rate (and it looks like it should be linear in n, or almost that)" -- in this case the mean is about $\log_2 n $, is that "reasonable" would you say?
Feb 3, 2013 at 3:55	vote	accept	burtonpeterj
Jan 17, 2013 at 12:48	history	answered	Ben Barber	CC BY-SA 3.0