Chapter 7: Discrete Probability

Question: What is the probability that that Bo, Colleen, Jeff, and Rohini win the first, second, third, and fourth prizes, respectively, in drawing if 50 people enter a contest and

(a) no one can win more than one prize.

(b) winning more than one prize is allowed.

Question: Prove the general case of Theorem 7. That is, show that if \({X_1},{X_2}, \ldots ,{X_n}\) are pairwise independent random variables on a sample space \(S\), where \(n\) is a positive integer, then \(V\left( {{X_1} + {X_2} + \cdots + {X_n}} \right) = V\left( {{X_1}} \right) + V\left( {{X_2}} \right) + \cdots + V\left( {{X_n}} \right)\). (Hint: Generalize the proof given in Theorem 7 for two random variables. Note that a proof using mathematical induction does not work; sec.

Question: The maximum satisfiability problem asks for an assignment of truth values to the variables in a compound proposition in conjunctive normal form (which expresses a compound proposition as the conjunction of clauses where each clause is the disjunction of two or more variables or their negations) that makes as many of these clauses true as possible. For example, three but not four of the clauses in

\((p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee r) \wedge (\neg p \vee \neg r)\)

can be made true by an assignment of truth values to\(p,q\), and\(r\). We will show that probabilistic methods can provide a lower bound for the number of clauses that can be made true by an assignment of truth values to the variables.

a) Suppose that there are\(n\)variables in a compound proposition in conjunctive normal form. If we pick a truth value for each variable randomly by flipping a coin and assigning true to the variable if the coin comes up heads and false if it comes up tails, what is the probability of each possible assignment of truth values to the\(n\)variables?

b) Assuming that each clause is the disjunction of exactly two distinct variables or their negations, what is the probability that a given clause is true, given the random assignment of truth values from part (a)?

c) Suppose that there are\(D\)clauses in the compound proposition. What is the expected number of these clauses that are true, given the random assignment of truth values of the variables?

d) Use part (c) to show that for every compound proposition in conjunctive normal form there is an assignment of truth values to the variables that makes at least\(3/4\)of the clauses true.

Question: Find each of the following probabilities when $\mathit{n}$independent Bernoulli trials are carried out with probability of success$\mathit{p}$.

a) The probability of no failures

b) The probability of at least one failure

c) The probability of at most one failure

d) The probability of at least two failures

Question:In roulette, a wheel with 38 numbers is spun. Of these, 18 are red, and 18 are black. The other two numbers, which are neither black nor red, are 0 and 00. The probability that when the wheel is spun it lands on any particular

number is 1/38.

(a) What is the probability that the wheel lands on a red number.

(b) What is the probability that the wheel lands on a black number twice in a row.

(c) What is the probability that wheel the lands on 0 or 00.

(d) What is the probability that in five spins the wheel never lands on either 0 or 00.

(e) What is the probability that the wheel lands on one of the first six integers on one spin, but does not land on any of them on the next spin.

Question: Use Chebyshev's inequality to find an upper bound on the probability that the number of tails that come up when a fair coin is tossed \(n\) times deviates from the mean by more than \(5\sqrt n \).

Question:What is the probability that each player has a hand containing an ace when the 52 cards of a standard deck are dealt to four players?

Question: Use Chebyshev's inequality to find an upper bound on the probability that the number of tails that come up when a biased coin with probability of heads equal to 0.6 is tossed \(n\) times deviates from the mean by more than \(\sqrt n \).

Question: Use mathematical induction to prove that ${\mathit{E}}_{\mathbf{1}}\mathbf{,}{\mathit{E}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{E}}_{\mathbf{n}}$ is a sequence of $\mathit{n}$ pair wise disjoint events in a sample space $\mathit{S}$, where $\mathit{n}$is a positive integer, then $\mathbf{}\mathit{p}\left({\cup }_{i=1}^n{E}_i\right)\mathbf{=}{\mathbf{\sum }}_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathit{p}\left(E_i\right)$.

Question:To determine which is more likely: rolling a total of 8 when two dice are rolled or rolling a total of 8 when three dice are rolled.