Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.