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 kth 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 nth 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 kth heads?

Let X be the number of flips until the kth 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 ith 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:
The linearity of expectations yields:

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,
    as I found this article at this web page.


  4. When I initially commented I clicked the
    “Notify me when new comments are added” checkbox and now
    each time a comment is added I get four e-mails with the same comment.
    Is there any way you can remove me from that service?



  5. It’s great that you are getting ideas from this article as well as from our dialogue made at this place.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: