CS 70 Discrete Mathematics for CS

Fall 2004  Rao  Midterm II Soln

Solutions to Midterm II

1. (a) m^{n}

(b) \binom{n}{k}

(c) n!

(d) \binom{n+k−1}{k−1}

(e) \binom{n+k−1}{k−1} − ∑ _{i=1}^{l−1} \binom{k}{i}\binom{n−1}{i−1} or ∑ _{i=l}^{k} \binom{k}{i}\binom{n−1}{i−1}

2. (a) p (b) p − p^{2}

(c) 1/4

(d) 2μ

(e) 2σ

(f) m\binom{n}{3}(\frac{1}{m})^{3}(1 − \frac{1}{m})^{n−3}

3. (a) (1 − p)^{i−1} p (b) \binom{n}{i}p^{i}(1 − p)^{n−i}

(c) 4

(d) [μ − σx,μ + σx]

4. (a) X is 100,000,000 with probability 0.01, and 0 otherwise.

(b)

μ = ∑_{a} aPr[Y = a]
= ∑_{a≠0} aPr[Y = a]
≤ ∑_{a≠0} 3μ/2 × Pr[Y = a]
= 3μ/2 × ∑_{a≠0} Pr[Y = a]
= 3μ/2 × (1 − Pr[Y = 0])

This implies Pr[Y = 0] ≤ 1/3.

5. Out of the six possible sides that we could have got, 3 are golden. Out of these, 2 belong to a pancake that’s golden on both sides. Therefore the probability the other side is golden is 2/3. Let A denote the event that both sides are golden, and B denote the event that the first side is golden.

Pr[A|B] = \frac{Pr[A ∩ B]}{Pr[B]}= \frac{1/3}{1/2} = 2/3

6. Let FAKE denote the event that the coin is fake, HEAD the event that we see a head in the first flip, and k-HEAD denote the events that we see k heads in k flips.

(a)

Pr[ FAKE | HEAD ] = Pr[ HEAD | FAKE ]Pr[ FAKE ] Pr[ HEAD ]

= \frac{1 × 1/n}{1 × 1/n + 1/2 × (n − 1)/n}
= \frac{2}{n + 1}

(b)

Pr[ FAKE |k-HEAD ] = Pr[k-HEAD | FAKE ]Pr[ FAKE ] Pr[k-HEAD]

= \frac{1 × 1/n}{1 × 1/n + (1/2)^{k}× (n − 1)/n}
= \frac{2^{k}}{n − 1 + 2^{k}}

(c) Let “fake” denote the event that the program outputs “fake”. The probability of error is the probability of saying “normal” when the coin is fake, and saying “fake” when the coin is normal. The first event never happens, i.e. it has 0 probability. So

Pr[ error ] = Pr[ “fake” ∪ normal coin ]
= Pr[ “fake”| normal coin ]Pr[ normal coin ]
= ( \frac{1}{2})^{k} \frac{n − 1}{n}