CS202: Discrete Structures

6.3: Probability Process

• Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability" URL

  Read Section 2, which presents a four-step process for solving probability problems. This process incorporates basic probability axioms, albeit indirectly, as part of the process steps.
  

• 6.3.1: Probability Axioms

  • University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions, and Graphs: Counting and Listing" URL

    Read Section 4 on pages CL-28 through CL-30.

    Some useful results are summarized here:

    ∑xε S P(x) = 1, where S is the sample space, also written P(S) = 1;

    P(x) >=0, for x in the sample space;

    Let E be an event, defined as a subset of S. P(E) = ∑xε EP(x);

    If E and D are events such that E is contained in D, then P(E) <= P(D); and

    P(E È D) = P(E) + P(D) for E, D disjoint.

    From the above the following can be proved: Let E be an event. E' = S -E. P(E È E') = P(E) + P(E'), P(S= E È E') = 1; thus, 1 = P(E) + P(E') and P(E') = 1 - P(E).

    Note: the probability of the complement of an event E is 1 - (probability of E). This result is often very useful, because for some problems the probability of E may be difficult to calculate, but the probability of the complement of E may be easy to calculate.
    

• 6.3.2: The Probability of a General Union of Two Events

  • Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Conditional Probability" URL

    Read Section 4, "Conditional Probability Pitfalls," in particular, "Conditional Probability Theorem 2" and "Theorem 3" on page 12. This will serve as a lead-in to conditional probability, which is covered in the next section.