2
$\begingroup$

We are given random bit generator which generates 0s and 1s with equal probability 1/2. We have an algorithm which generates random numbers using this random bit generator in this way: we look for subsequences of 1s, and length of each subsequence gives us one random number (lets forget that this is really bad random generator).

So for example: 0011011100010 gives us random numbers [2, 3, 1]

Task is to show that probability of seeing number greater than $c+\log_2n$ is falling exponentially for $c\in\mathbb{N}$

Intuitively every time we increased $c$ for one, there is $1/2$ probability that next bit is going to be 1, so probability is falling exponentially, but I guess I have to prove that expected longest run of ones in sequence is going to be $\log_2n$

Here is an article about distribution of longest run in coin flip (we can se our random bit generator as fair coin flip). On page 6 is given an approximation for length of longest run, but thing that bothers me is that in an article, n is number of all trials, while in this task, n is number of subsequences of ones (equals number of "random numbers"), while number of trials can be much larger.

1 Answers 1

0

Your question based on the number of $1$s [each with probability $\frac12$], rather than the number of trials, is equivalent to the paper's "longest run of heads or tails" applied to a fair coin, and in particular where it gives $B_n (x) = 2 A_{n-1}(x-1)\qquad \qquad (2)$ and explains this by saying

... the distribution of the longest run of heads or tails is simply the distribution of the longest run of heads alone for a sequence containing one fewer coin toss, shifted to the right by one.