This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

cs-401r:assignment-1 [2014/09/05 10:12] ringger |
cs-401r:assignment-1 [2014/09/24 15:40] (current) cs401rPML [Question 3: Useful theorems in probability theory] added link to example proofs |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | '''Probability Theory''' | + | = Probability Theory = |

== Objectives == | == Objectives == | ||

Line 10: | Line 10: | ||

== Instructions == | == Instructions == | ||

- | This is a mathematical homework assignment. Show your work. Be clear and concise. Type your assignment.<br> | + | This is a mathematical homework assignment. Show your work. Be clear and concise. Type your assignment. |

I strongly recommend you work through these exercises as soon as possible for their instructional content. If you have general questions about the assignment, please post on the Google Group. Finish early, and earn the early bonus. | I strongly recommend you work through these exercises as soon as possible for their instructional content. If you have general questions about the assignment, please post on the Google Group. Finish early, and earn the early bonus. | ||

Line 16: | Line 16: | ||

== Exercises == | == Exercises == | ||

- | === Question 1: Useful theorems in probability theory === | + | === Question 1: Warming up === |

- | [30 points; 10 per sub‐problem] | + | [10 points: 2 for the first, 3 each for the second and third parts] |

- | (Adapted from: Manning & Schuetze, p. 59, exercise 2.1) | + | Let's begin with the same sample space $\Omega$ we have been using in class: Let $\Omega$ be the set of all outcomes defined by three successive coin flips. Assume that the coin is fair and that the distribution over all singleton events (events containing one outcome) is uniform. Let the event $D$ be the set of all outcomes in which the second flip is a head. Let the event $E$ be the set of all outcomes in which the final flip is a tail. |

- | | + | # What are $P(D)$, $P(E)$, and $P(D \cap E)$ ? |

- | Use the [[Set Theory Identities]] and [[Axioms of Probability Theory]] to prove each of the following five statements. Develop your proof first in terms of sets and then translate into probabilities; use set theoretic operations on sets and arithmetic operators on probabilities. Be sure to apply [[Proofs|good proof technique]]: justify each step in your proofs; set up your proofs in two-column format, with each step showing a statement on the left and a justification on the right. Remember that in order to invoke an axiom as justification, you must first satisfy the conditions / pre-requisites of the axiom. | + | # What is $P(D|E)$ ? |

- | # \begin{equation}P(B - A) = P(B) - P(A \cap B)\end{equation} | + | # What is $P(E|D)$ ? |

- | # <math>P(A \cup B) = P(A) + P(B) - P(A \cap B)</math> (the addition rule) | + | |

- | #* Hint: refer to part result #1 as a part of your proof of part #2 | + | |

- | # <math>P(\neg A) = 1 - P(A)</math> | + | |

- | #* Hint: refer to part result #1 as a part of your proof of part #4 | + | |

=== Question 2: Joint Probability === | === Question 2: Joint Probability === | ||

Line 36: | Line 32: | ||

* Let <tt>is-abbreviation</tt> denote the event "this period indicates an abbreviation", and let <tt>three-letter-word</tt> denote "a period occurs after a three letter word" | * Let <tt>is-abbreviation</tt> denote the event "this period indicates an abbreviation", and let <tt>three-letter-word</tt> denote "a period occurs after a three letter word" | ||

* Assume the following probabilities: | * Assume the following probabilities: | ||

- | ** <math>P(</math><tt>is-abbreviation</tt><math> | </math><tt>three-letter-word</tt><math>) = 0.8</math> | + | ** $P($<tt>is-abbreviation</tt>$ | $<tt>three-letter-word</tt>$) = 0.8$ |

- | ** <math>P(</math><tt>three-letter-word</tt><math>) = 0.0003</math> | + | ** $P($<tt>three-letter-word</tt>$) = 0.0003$ |

+ | | ||

+ | === Question 3: Useful theorems in probability theory === | ||

+ | [60 points; 20 per sub‐problem] | ||

+ | | ||

+ | (Adapted from: Manning & Schuetze, p. 59, exercise 2.1) | ||

+ | | ||

+ | Use the [[Set Theory Identities]] and [[Axioms of Probability Theory]] to prove each of the following five statements. Develop your proof first in terms of sets and then translate into probabilities; use set theoretic operations on sets and arithmetic operators on probabilities. Be sure to apply [[Proofs|good proof technique]]: justify each step in your proofs; set up your proofs in two-column format, with each step showing a statement on the left and a justification on the right. Remember that in order to invoke an axiom as justification, you must first satisfy the conditions / pre-requisites of the axiom. See the proofs on the [[example_proofs|example proofs page]]. | ||

+ | # $P(B - A) = P(B) - P(A \cap B)$ | ||

+ | #* Note that inside the $P(\cdot)$, the '$-$' operator indicates set difference. | ||

+ | # $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ (the addition rule) | ||

+ | #* Hint: use the theorem in part #1 as a step in your proof | ||

+ | # $P(\overline{A}) = 1 - P(A)$ | ||

+ | #* Hint: use the theorem in part #1 as a step in your proof | ||

- | === Question 3: Factoring Joint Distributions === | + | === Question 4: Factoring Joint Probabilities === |

[10 points] | [10 points] | ||

- | # How many possible ways can you completely factor the joint distribution <math>P(X_1, X_2, X_3, X_4, X_5, X_6)</math>? | + | # How many possible ways can you completely factor the joint probability of six events $P(A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6)$ |

- | # For some arbitrary joint probability distribution on six random variables <math>P(X_1, X_2, X_3, X_4, X_5, X_6)</math>, apply the chain rule to completely factor this distribution in one way. | + | # Apply the chain rule to completely factor the joint probability $P(A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6)$ in one way. |

- | === Question 4: Conditional Probability === | + | === Question 5: Conditional Probability === |

[10 points] | [10 points] | ||