Probability and Computing: Chapter 2 Exercises (Cont. 1)

Exercise 2.14: The geometric distribution arise as the distribution of the number of times we flip a coin until it comes up heads. Consider now the distribution of the number of flips $X$ until the $k$th head appears, where each coin flip comes up heads independently with probability $p$. Prove that this distribution is given by

$Pr(X=n) = \binom{n-1}{k-1}p^{k}(1-p)^{n-k}$

for $n \geq k$. (This is known as the negative binomial distribution.)

The formula comes naturally when we consider the probability exactly $k-1$ heads happen in a sequence of $n-1$ flips(the last $n$th flip is heads).

Exercise 2.15: For a coin that comes up with head independently with probability $p$ on each flip, what is the expected number of flips until the $k$th heads?

Let $X$ be the number of flips until the $k$th heads.
We can solve this exercise by using the definition formula of expectation:

$E[X]=\sum_{i=1}^{\infty}iPr(X=i) = \sum_{i=1}^{\infty}i\binom{i-1}{k-1}p^{k}(1-p)^{i-k}$,

but there is another way to work around it.
Let $X_{i}$ be the number of flips needed to get the $i$th heads when we already had exactly $i-1$ heads. Clearly $X=\sum_{i=1}^{k}X_{i}$.
Each $X_{i}$ is a geometric random variable with parameter $p$. So we have:
$E[X_{i}]=\frac{1}{p}$.
The linearity of expectations yields:
$E[X]=E[\sum_{i=1}^{k}X_{i}]=\sum_{i=1}^{k}E[X_{i}]=\sum_{i=1}^{k}\frac{1}{p}=\frac{k}{p}$.

Exercise 2.16: Suppose we flip a coin $n$ times to obtain a sequence of flips $X_{1},X_{2},\ldots ,X_{n}$. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if $X_{3}$, $X_{4}$, and $X_{5}$ are all heads, there is a streak of length $3$ starting at the third flip.(If $X_{6}$ is also heads, then there is also a streak of length $4$ starting at the third flip.)

(a) Let $n$ be a power of $2$. Show that the expected number of streaks of length $log_{2}n+1$ is $1-o(1)$.

(b) Show that, for sufficiently large $n$, the probability that there is no streak of length at least $\lfloor log_{2}n-2log_{2}log_{2}n \rfloor$ is less than $1/n$.(Hint: Break the sequence of flips up into disjoint blocks of $\lfloor log_{2}n-2log_{2}log_{2}n\rfloor$ consecutive flips, and use that the event that one block is a streak is independent of the even that any other block is a streak.)

5 responses to this post.

1. Hello there! This is kind of off topic but I need some help from an established blog.
Is it very difficult to set up your own blog? I’m
not very techincal but I can figure things out pretty quick.
I’m thinking about creating my own but I’m not sure where to begin. Do you have
any points or suggestions? Thank you

2. I am in fact thankful to the holder of this web site who has shared this wonderful piece of writing at here.

3. It’s very straightforward to find out any matter on web as compared to textbooks,