Practice problems 2 You should also read the lecture notes and homework solutions. There are many many problems here many of which have been covered in section. I am throwing them out to give lots of practice.

1. We have k distinct red beads and k distinct black beads. In how many ways can the beads be arranged around the edge of a circular table so that they alternate in color? In how many ways can they be strung on a necklace so that they alternate in color?

2. Answer the previous question assuming that all the beads of one color are together in a row (in place of the assumption that the beads alternate in color).

3. Prove that

∑_{i=0}^{n} \binom{n}{i} ∑_{j=0}^{n−i} \binom{n − i}{j} = 3^{n}.

(Hint: consider the number of ways of splitting n elements into 3 groups.)

4. Throw n balls into n bins.

(a) What is the probability that the first bin is empty?

(b) What is the probability that the first k bins are empty?

(c) What is the probability that the second bin is empty given that the first one is empty?

(d) Are the events that “the first bin is empty” and “the first two bins are empty” independent?

(e) What is the expected number of empty bins?

(f) What is the expected number of bins containing exactly one ball?

5. There are n bins.

(a) We keep throwing balls into these bins until every bin contains at least one ball. What is the expected number of balls we have to use?

(b) We keep throwing balls into these bins until half of the bins are not empty. What is the expected number of balls we have to use?

(c) Show that the probability that there exists some bin containing at least three balls when throwing n^{2/3} balls into n bins is at most 1/6?

6. There are three mutually independent events: A,B, and C. The probability that event A occurs is 0.4, the probability that event B occurs is 0.6, and the probability that event C occurs is 0.3. Calculate the following.

(a) P r[A|B].

(b) P r[A ∩ B].

(c) P r[A ∪ C].

(d) P r[B ∩ C].

(e) P r[A ∩ B ∩ C].

(f) P r[A ∪ B ∪ C].

7. A city of (n) × (m − 1) blocks has n + 1 two-way avenues (going North-South) and m two-way streets (going West-East). Each street consist of n parts; the 1st part is from its intersection with the first avenue and with the second avenue, and the i-th part is from its intersection with the i-th avenue to the intersection with (i + 1)-th avenue.

(a) Every Wednesday, the city decides to close each part of each street independently with probability p. All avenues are opened. To get from the West side of the city to the East side, one needs to go through only opened parts of the streets and avenues, i.e., no one can get to the East side if, for some j, the j-th parts of all the streets are closed. What is the probability that a person cannot go from the west side to the east side on Wednesday?

(b) On every Sunday, the city decides to make all parts of the streets one-way. Independently, for each part, the city randomly assign the direction either East-West or West-East. My house is on the West side of the city. I want to go from my house to the East side and come back to my house. What is the probability that I can do so?

8. Burnt pancakes I have a bag containing three pancakes: One golden on both sides, one burnt on both sides, and one golden on one side and burnt on the other. You shake the bag, draw a pancake at random, look at one side, and notice that it is burnt. What is the probability that the other side is burnt? Show your work.

9. What is the expected value of the sum of the values of a 6 sided die, a 4 sided die and a 20 sided die?

10. What is the expected value of X for a geometrically distributed variable with parameter p? What is the variance of X?

11. What is the expected value of X for a binomially distributed variable with parameters n and 1/2. What is the variance of X?

12. A coin having probability p of landing heads is flipped until the head appears for the r-th time. Let X denote the number of flips required. Compute the expectation of X.

13. I am on a line in the bank. There are 5 people ahead of me. The service time for each customer depends on the type of the transaction. There are 3 types, each occurring equally likely. For transaction type A, it takes 3 minutes; for type B, 5 minutes; and for type C, 1 minutes.

(a) What is the expected time I have to be on the line?

(b) Let a random variable X denote the service time for a customer. Compute the variance of X?

(c) What is the variance of the time I have to be on the line? (Hint: each customer is independent.)

(d) What is the expected time I have to be on the line, if I know that no one ahead of me has transaction type A?

14. There are m jobs randomly scheduled to n servers.

(a) What is the expected number of jobs the first server receives?

(b) Use Markov’s Inequality to show that the probability that the first server receives more than 2m/n jobs with probability less than 1/2.

(c) Let r.v. X denote the number of jobs the first server receives. Show that the variance of X is m(\frac{1}{n})(1 − \frac{1}{n}).

(d) Use Chebyshev’s Inequality to show that the probability that the first server receives more than m/n + 2\sqrt{m/n} jobs is less than 1/4.

15. Show that the probability for a positive random variable being twice its expected value is at most 1/2.

16. Show that the probability for a positive random variable X being greater than aE(X) is at most 1/a.

17. Is Markov’s theorem tight? Give a distribution for a random variable where the probability of being twice the average is exactly 1/2.

18. Give a distribution for a random variable where the expectation is 1/2 and the probability that it is greater than or equal to 1 is 2/3.

19. For a random variable X with expectation μ and variance σ, put in TRUE/FALSE/MAYBE in the following statements. (I messed this problem up. Variance should be σ^{2}.—jittat.)

(a) The probability that X is greater than 2μ is less than 1/2.

(b) The probability that X is greater than 10μ is more than 1/5.

(c) The probability that X is greater than μ is 1/2.

(d) The probability that X is smaller than μ is 1/2.

(e) The probability that X is greater than 3μ/2 is less than \frac{σ}{(μ/2)^{2}} .

(f) The probability that X is smaller than μ/2 is greater than \frac{σ}{(μ/2)^{2}} .

(g) The probability that X is greater than μ/2 is at least 1 − \frac{σ}{(μ/2)^{2}} .

(h) The probability that X is greater than μ + 2\sqrt{σ} is less than 1/4.

(i) The probability that X is with in μ ± 2\sqrt{σ} is lessthan 1/4.

20. Put in TRUE/FALSE/MAYBE in the following statement.

(a) For a geometric random variable with parameter p, the probability that the variable is larger than 2 is 1 − p.

(b) For a binomial random variable with parameter n and p, the expected value of the variable is np.

(c) For a binomial random variable with parameter n and p, the probability that the variable is larger than 2np is more than 1/2.

(d) For a binomial random variable with parameter n and p, the probability that the variable is larger than np − 2\sqrt{np(1 − p)} is more than 3/4.

(e) For a Poisson random variable with parameter λ, the probability that the variable is within λ ± a\sqrt{λ} is at least 1 − \frac{1}{a^{2}} .

(f) For a Poisson random variable with parameter λ, the probability that the variable is smaller than λ + 2\sqrt{λ} at most \frac{1}{2}.

(g) For a Poisson random variable with parameter λ, the probability that the variable

is smaller than 2λ is more than 3/4.

21. State and prove Markov’s theorem.

22. State and prove Chebyshev’s theorem.

23. We want to estimate the proportion p of the engineering students in the UC. How large does the sample size n have to be to ensure a relative error of 0.1 with confidence 90%, if you know that p > 0.2.

Many of the following were solved in section.

24. Prove the following combinatorial idenitties:

(a) \binom{n}{r} = \binom{n}{n−r}

(b) \binom{n}{r−1} + \binom{n}{r} = \binom{n+1}{r}

(c) ∑_{r=0}^{n} \binom{n}{r} = 2^{n}

(d) \binom{m+n}{r} = ∑_{k=0}^{r} \binom{m}{r−k}\binom{n}{k}

(e) \binom{2n}{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}

25. Suppose you want to buy n fruits. In how many ways can you do that if:

(a) There are apples and oranges at the market and you buy at least one of each.

(b) There are apples, oranges and bananas at the market and you buy at least one of each.

(c) There are k kinds of fruits at the market, and you buy at least one of each.

26. What is the number of strings you can construct given:

(a) n ones, and m zeroes.

(b) n_{1} A’s, n_{2} B’s and n_{3} C’s.

(c) n_{1}, n_{2}, …, n_{k} respectively of k different letters.

27. Suppose you want to buy n fruits. This time you can also buy 0 of any kind In how how many ways can you do that if:

(a) There are apples and oranges at the market.

(b) There are apples, oranges and bananas at the market.

(c) There are k kinds of fruits at the market.

28. Two squares are chosen at random on 8 × 8 chessboard. What is the probability that they share a side?

29. A man speaks the truth 3 out of 4 times. He flips a coin that has bias Heads : Tails = 1 : 2 and reports it’s Heads. What is the probability it is Heads?

30. A bulb will last at least 150 days with probability 0.7 and it will last at least 160 days with probability 0.2. What is the probability it will last between 150 and 160 days?

31. A box contains tickets numberes 1, 2, …, N. m tickets are drawn with replacement. What is the probability that the largest number drawn is k?

32. Box A contains 1 black and 3 white marbles, and box B contains 2 black and 4 white marbles. A box is selected at random, and a marble is drawn at random from the selected box.

(a) What is the probability that the marble is black?

(b) Given that the marble is white, what is the probability that it came from the box A?

33. Three prisoners A, B and C are in jail in separate cells. One of them is sentenced to death, but they don’t know who. The other two will walk free. The guard knows who is the unfortunate prisoner. A writes a letter to his wife just in case he’s the one to die, and asks the guard to give the letter to one of the other prisoners, who’s walking free. The next day he asks the guard if he gave the letter, and the guard responds “Yes, I gave it to B.” A is suddenly upset because he feels that now it’s only between him and C, and so his chance of dying has increased from 1/3 to 1/2. Does he have a reason to be upset? Explain.

34. n guests at a party are handed back their n hats at random.

(a) What is the expected number of people who get their own hat.

(b) What is the expected number of pairs of people who’ll need to swap hats

(c) What is the expected number of k-tuples of people who can stand in a circle and each hand their hat to the person on their left.

(d) What is the expected total number of circles that will form this way (a person who has got his own hat is a circle of length 1, a pair of people who swap hats are a circle of size 2, etc.)

35. We roll a die n times

(a) What is the expected number of times you roll at least a 5?

(b) What is the expected sum of rolls on which you got at least 5?

36. (a) There are n random people, each is equally likely to be a boy or a girl, and equally likely to have blue or brown eyes, independent of the gender. What is the probability that there is no girl with blue eyes?

(b) S is a set of n elements, and P and Q are subsets of S. In how many ways can we choose P and Q so that P ∩ Q = ∅?

37. Given a random bitstring of length 2n + 1, what is the probability it contains at most n 1’s?

38. I write a letter to my friend and don’t receive a reply. One out of m letters gets lost in the mail. What is the probability my friend received my letter, assuming that if he did, he would reply?

39. There are three people: A,B, and C. The experiment is the following. A flips a fair coin. B also flips a fair coin. C looks at A’s result and if A gets Head, he flips a fair coin; otherwise, he uses B’s result. Which of the following pairs of events are independent?

(a) “A gets Head” and “B gets Tail”.

(b) “A gets Head” and “C gets Head”.

(c) “A gets Tail” and “C gets Tail”.

(d) “B gets Head” and “C gets Tail”.

40. A factory has 3 departments: A, B, and C. There are 3 machines in department A, 4 machines in department B, and 2 machines in department C. For each day, each machine fails independently with probability p. Only when every department has at least one working machine, the factory can assembly the product. What is the probability that for a given day, the factory can assembly the product?

41. Consider that two pollsters are attemptying to measure the support for candidate A who has 50% support. Say that each pollster by taking 100 samples of a random 0-1 variable, where the expectations are 49% for one pollster and 47% for the other. Estimate the probability (within 10%) that the “best” pollster (the one whose random variable associated with his sampling process is closest to 50%) gets closer to the true value for the support for the candidate. (You may assume that the distribution of the samples have converged to the normal distribution as specified in the Central Limit Theorem.)

42. What if each pollster took 1000 samples?