## 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}$

Thus,

$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. […] Webに転がってる解答 https://thethong.wordpress.com/2009/09/17/probability-and-computing-chapter-1-exercises/ を一部修正しただけですが． […]

2. 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

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

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

4. 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.

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

6. 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.

7. 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.

8. 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.

9. 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!

10. 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?

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

What web host are you using? Can I am getting your associate
lol

12. 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.

13. 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!!

14. 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.

15. 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.

16. 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.

17. 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!

18. 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.

19. 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
post…

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

21. 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.

22. 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
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