Probability and Computing: Chapter 1 Exercises

Exercise 1.5:

Let E_{n,m} be the event that Bob’s number is n and Alice ‘s number is m; E be the event that Alice wins.

(a): E = Pr(E_{1,2}) + Pr(E_{1,4}) + Pr(E_{1,9}) + Pr(E_{6,9}) + Pr(E_{8,9}) =\frac{5}{9}

(b): E = Pr(E_{2,3}) + Pr(E_{2,5}) + Pr(E_{2,7}) + Pr(E_{4,5}) + Pr(E_{4,7}) =\frac{5}{9}

(c): E = Pr(E_{3,6}) + Pr(E_{3,8}) + Pr(E_{5,6}) + Pr(E_{5,8}) + Pr(E_{7,8}) =\frac{5}{9}

Exercise 1.6:

Let E_{k,n} be the event that there are k white balls (in a total off n balls) in the bin, B be the event that we pick out black ball, W be the event that we pick out white ball at one turn.
We will prove by induction the following statement:

Pr(E_{1,n}) = Pr(E_{2,n})=...=Pr(E_{n-1,n})

– The statement is true for n= 2

– Assume that the statement is true for some n=k\ge 2 :

Pr(E_{1,k}) = Pr(E_{2,k})=...=Pr(E_{k-1,k}).

We will prove that it will aslo be true for n = k + 1, that is :

Pr(E_{1,k + 1}) = Pr(E_{2,k + 1})=...=Pr(E_{k,k + 1})

– Indeed, we have:

Pr(E_{1, k + 1}) = Pr(B\mid E_{1,k}) = \frac{k-1}{k}.

Pr(E_{2,k + 1}) = Pr(B \mid E_{2,k}) + Pr(W \mid E_{1,k}) = \frac{k-2}{k} + \frac{1}{k} = \frac{k - 1}{k}.

In general:

Pr(E_{i,k + 1}) = Pr(B\mid E_{i,k}) + Pr(W\mid E_{i -1,k}) = \frac{k-i}{k} + \frac{i-1}{k}=\frac{k-1}{k}


Pr(E_{1,k + 1}) = Pr(E_{2,k + 1})=...=Pr(E_{k,k + 1})=\frac{k-1}{k}

Base on induction, the first statement is true.


22 responses to this post.

  1. Posted by Anonymous on September 8, 2011 at 2:57 pm

    I have a different answer for this problem. when the white ball is just 1, so the probability for this situation is : 1/2 * 2/3 * 3/4……..*(n-1)/n = 1/n ,where n is the total numbers of bin. For the other sitution ,the answer is the same


  2. Posted by Anonymous on May 25, 2012 at 11:49 pm

    ex5 very simple but ínteresting. Alice always has choice to win


  3. Good post. I learn something new and challenging
    on sites I stumbleupon every day. It’s always exciting to read through content from other writers and use something from other web sites.


  4. It’s very easy to find out any topic on web as compared to textbooks, as I found this paragraph at this web page.


  5. What’s Taking place i am new to this, I stumbled upon this I’ve discovered It
    absolutely useful and it has helped me out loads. I hope to give a contribution & aid other
    users like its aided me. Great job.


  6. We stumbled over here from a different web address and thought I might as well
    check things out. I like what I see so now i am following you.
    Look forward to going over your web page again.


  7. My partner and I stumbled over here by a different web page
    and thought I may as well check things out.
    I like what I see so now i am following you. Look forward to checking out your web page again.


  8. Wow! This blog looks exactly like my old one! It’s on a entirely different topic but it has pretty much the same page layout and design. Great choice of colors!


  9. Currently it sounds like Drupal is the best blogging platform out there right now.

    (from what I’ve read) Is that what you’re using on your blog?


  10. Great blog here! Also your web site a lot up fast!

    What web host are you using? Can I am getting your associate
    hyperlink in your host? I wish my site loaded up as quickly as yours


  11. It’s in reality a nice and useful piece of info. I am happy that you simply shared this helpful information with us. Please stay us up to date like this. Thanks for sharing.


  12. Hello, i think that i saw you visited my site so i came to return the favor?
    .I am trying to to find issues to enhance my site!
    I suppose its good enough to use a few of your ideas!!


  13. Movie fans have been privileged over the years to view some incredible movies regarding the great sport
    of boxing. These are my personal favorites as best friend movies.
    The two main characters are Bob the Tomato and Larry the Cucumber.


  14. I love what you guys are up too. This kind of clever work
    and coverage! Keep up the superb works guys I’ve included you guys to my own blogroll.


  15. Hi, I do think this is a great web site. I stumbledupon it 😉
    I am going to return once again since I saved as a favorite it.
    Money and freedom is the greatest way to change, may you be rich and continue to help other people.


  16. You really make it seem so easy along with your presentation however I
    to find this matter to be really one thing which I think I’d never understand. It sort of feels too complex and very wide for me. I am having a look ahead on your subsequent post, I will try to get the hang of it!


  17. Its such as you read my mind! You appear to understand a
    lot approximately this, such as you wrote the guide in it or something.
    I feel that you simply can do with some % to drive the message home a bit, however instead of that, that is wonderful blog.

    A great read. I will definitely be back.


  18. I want to to thank you for this very good read!! I certainly loved every little bit of
    it. I have you book-marked to look at new things you


  19. I think the admin of this website is genuinely working hard for his site, since
    here every data is quality based material.


  20. It’s really very complicated in this active life to listen news on TV, thus I simply use
    the web for that reason, and get the newest news.


  21. I leave a response when I like a post on a site or if I have
    something to valuable to contribute to the discussion.
    Usually it is caused by the fire displayed
    in the post I browsed. And after this article Probability and
    Computing: Chapter 1 Exercises | Computer Science Blog. I was actually excited enough to drop a
    comment 🙂 I do have some questions for you if it’s okay.
    Could it be only me or does it give the impression like a few of
    these remarks appear as if they are left by brain dead people?
    😛 And, if you are writing at other sites, I’d like to
    follow everything new you have to post. Would you list the complete urls of your shared sites like your Facebook
    page, twitter feed, or linkedin profile?


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: