CS 237
                                                                                 Fall 2007


                                        Midterm With Answers

I. Multiple choice, short-answer (3 or 4 points each, total of 20).  
Do all 6 of the problems.
There will be no partial credit for the first 4 problems. 

Write all answers in your blue book.

1. Let A and B be events with Pr(A) = .3, Pr(B) = .6, Pr(A intersect B) = .2
and Pr(A-bar intersect B) = .4

Then Pr(A union B) = 

a .4              b .5         c .6            d  .7          e  .9 

Answer: d


2.  What is the variance of the random variable X whose values are 2, 3, 
-2,  and -4 where the probabilities of these values occurring are given by


X               2        3           -2           -4

pr(X)        1/8        1/2        1/8         1/4

a. 9 1/4               b. 9 1/2      c. 8 3/4           d. 10 1/8     e. None of the above 

Answer: a

3. A bowl contains 3 red chips and two blue chips.
You pick chips from the bowl (without replacement) until you get a blue chip.
What is the expected number of picks required ?

a. 1.8                  b. 2         c. 2.4                   d. 3             e. 3.2
 
Answer: d


4. 
You own an I-Pod factory where you have 2 machines M1 and M2
which produce the I-Pods.

M1 produces 30% of the I-Pods you make and M2 the
other 70%.

Furthermore, 4% of M1's I-Pods are defective while 2% of M2's I-Pods
are defective.

If you randomly select an I-Pod you  produced and it is defective,
what is the probability that it was produced by machine M1 ?

a. 6/13         b. 1/2          c. 2/3           d. 5/11      e. 6/10

Hint: Use Bayes' Theorem.

Answer: a

5. In any game, the probability that the Red Sox will beat the Rockies is .6.

What is the probability that the Red Sox will win a 4 out of 7 game 
series with the Rockies ? Note that the way such a series is played is that
the first team to win 4 games wins the series. 

(You need not calculate the exact number here, but you should write
an equation whose value is the exact probability.)

Answer: 

Let A = prob (Red Sox win 4 straight games) = (.6)^4
B= prob (RS win 4 of 5 games) = (.6)^4 x (.4)
C= prob (RS win 4 o6 games) = (.6)^4 x (.4)^2
D = prod (RS win 4 of 7 games) = (.6)^4 x (.4)^2

Answer: Pr( Red Sox win the series ) = A + 4B + 10C + 20D

6. Let X be a random variable with expected value 40 and unknown variance.

Use the Chebyshev inequality to find a value for the variance var(X) 
which is bigger than 1 and which results in
pr(X is between 35 and 45) >= .9

Answer:

We want to find V = Var(X) as above. 

We have E[X] = 40 and let a =5 in the Chebyshev inequality. 

This gives:  pr(|X-40|>=5) <= V/25

pr(|X-40|>=5) = pr (X <= 35 or X >= 45) = 1-Pr(35 <= X <= 45)

So  1-Pr(35 <= X <= 45) <= V/25, and solving this equation for 
Pr(35 <= X <= 45) gives Pr(35 <= X <= 45) >= 1 - V/25. 

We want this probability >= .9, so setting 1 - V/25 = .9 gives 
V = 2.5, so any V between 1 and 2.5 works to answer this question.


II. Short Answer, each problem is worth 10 points (20 points total).
.br

Do 2 out of the following 3 problems. Write the numbers of the 
2 problems you want graded on the outside of your blue book. 

7. Say a Vector V of n integers has a majority element (an ME) 
if there is one number that appears more than (2/3)n times in the vector. 
We want to decide if the vector V has a majority element and 
the value of that element if does does.

Probabilistic ME Algorithm:  The Input is a Vector V of length n.

1. Choose a random element of V by choosing number k between 1 to n, 
uniformly at random, and letting  VALUE the number $k sup{th}$ element of V.
.br

2. Now compare every element of V with VALUE and let COUNT be  the 
number of element in V equal to VALUE.

3. Output: 

3a. If C > (2/3)n then output "V has a majority element and VALUE is that element." 

3b. Otherwise output "V has no majority element."


i. Explain when the algorithm answers correctly and when it might 
answer incorrectly.

Answer: The algorithm is always correct if it outputs a value in 3a, as it 
has already checked that the value is an ME. 

What is the probability that the ME algorithm answers correctly ? 

Answer: The algorithm is incorrect with probability <= 1/3,
so it is correct with probability 2/3 (in the worst case). 

That is, give a bound on the probability that ME answers correctly
in the worst case. Explain your reasoning.


(For example, you might claim that, for some specific F, "For any 
list of n numbers, 
ME answers correctly at least F of the time." Here F is a fraction 
between 0 and 1.)
.br

 Now consider the following "repeated ME algorithm."

Iterated ME Algorithm: The Input is a vector  V, as before.

1. Repeat the ME algorithm above on V t times. 

2. If after any of the t runs of the algorithm, the algorithm gives an 
output at step 3a, then output the same thing. 

Otherwise output "V has no majority element."


Now what is the probability that the iterated ME algorithm answers correctly ?

Repeating the Me algorithm independently t times yield 
pr( iterated algorithm is incorrect) <= (1/3)^t.

So pr (iterated algorithm is correct) >= (2/3)^t .

8. We are holding a "blind" auction among n people.

The auction system works as follows. Each of the people pick a 
positive integer as the amount they are willing to bid. (Assume for
this problem that no two people pick the same amount to bid. )

Now the auctioneer chooses a random order in which to process the 
bidders and figure out the value of the highest bid.

Initially the auctioneer sets Value=0.
The auctioneer then chooses a random order of all the bidders
and goes through the bidders one by one in this order. 

For each bidder the auctioneer gets their bid, and sees if this
new bid is the highest bid received so far. If so Value is updated to the
new bid. After all bidders have been considered, the last bid which caused an update is output as the highest bid.

So or example, if the bidders bid 50, 60 and 25 in that order,
then the bid is updated twice, for 50, and then 60, but not for 25.
So the output is 60, and the bid was updated twice.  

What is the expected number of times that the auctioneer 
will update the bid. 

Show your work. 

Answer: Define X  to be the random variable whose value is the 
number of times the auctioneer updates the bid during the algorithm above. 
So the goal is to calculate E(X).

Now define n independent indicator random variables by, Xi = 1 if 
the ith bid causes the auctioneer to update Value, and 0 if not. 
Clearly, X = (X1 + X2 + .... + Xn), and by linearity of expectation
E(X) = (E(X1) + E(X2) + .... + E(Xn)). 

Now E(Xi) = 1/i, since the order the bids are processed is chosen uniformly
at random and since 1/i = (i-1)!/i! is the probability that in a randomly 
chosen sequence of bids, the ith bid causes an update.

SO, E(X) = (E(X1) + E(X2) + .... + E(Xn)) = (1 + 1/2 + 1/3 +... + 1/n)
= H(n), and for all n, ln n - 1 <= H(n) <= ln n + 1. 

9. You are given a probability space with sample space 
S={a,b,c,d,e} and where the 5 elementary  events in S have probability

pr({a}) = pr({b}) = pr({c}) = 1/4 and pr({d}) = pr({e}) = 1/8

Let A={a, d, e}, B = {b, d, e}, C = {c, d, e} be events.

i. Show that A, B and C are pairwise independent.

Answer: 

S and T are pairwise independent if pr (S intersect T) = pr(S) x pr(T)

Pr(A) = Pr(B) = Pr(C) = 1/2 
Pr(A intersect B) =Pr(A intersect C) =Pr(B intersect C ) = pr({d,e}) = 1/4
and  Pr(A)  x Pr(B) = Pr(A) x Pr(C) = Pr(B) x Pr(C) = 1/4


ii. Are A, B and C independent ? Why or why not ?

Answer: Pr(A) x Pr(B) x Pr(C) = 1/8 which is not equal to
Pr(A intersect B intersect C) = 1/4.

iii. Define a random variable on S by 

X(a) = 1, X(b) = 2, X(c) = 3, X(d) = 8, X(e) = 4.

What is pr(X > E[X]) ?

Answer: E[X] = 3 and

pr(X > 3) = pr({d,e}) = 1/4