CSC165 Discrete Structure

Discrete StructureUnit 1114 min read

Probability Basics, Conditional Probability & Applications

Unit 11 of Discrete Structure covers fundamental probability concepts, conditional probability rules (Bayes' Theorem, independence), and real-world applications like medical testing, spam filtering, and combinatorial problems—essential for TU exams with 20% weight on problem-solving.

TAKEAWAYS:

  • Understand sample space (S), events (E), and probability axioms (P(E) ∈ [0,1], P(S)=1) as the foundation for all calculations.
  • Master conditional probability and its independence condition ().
  • Apply Bayes’ Theorem to reverse probabilities in medical testing or spam detection.
  • Solve combinatorial probability problems using with permutations/combinations.
  • Recognize applications in risk assessment (e.g., "How many ways can you invite 6 out of 9 families?" uses combinations).
  • Memorize common pitfalls: ignoring sample space constraints, misapplying independence, or confusing vs. .

1. Probability Basics

1.1 Definitions

  • Experiment: A procedure with well-defined outcomes (e.g., rolling a die, flipping a coin).
  • Sample Space (S): Set of all possible outcomes. Example: For a die, .
  • Event (E): A subset of . Can be simple (single outcome) or compound (multiple outcomes). Example: (even numbers).
  • Probability Axioms (Kolmogorov):
    1. for any event .
    2. .
    3. For mutually exclusive events , .

1.2 Probability of an Event

For finite sample spaces, probability is calculated as: Worked Example: Problem: What is the probability of drawing a king from a standard deck of 52 cards? Solution:

  • Favorable outcomes = 4 (kings of hearts, diamonds, clubs, spades).
  • Total outcomes = 52.
  • .

1.3 Key Properties

Property Formula Example
Complement Rule
Addition Rule (Mutually Exclusive) (for die)
Addition Rule (General) Overlapping events

2. Conditional Probability

2.1 Definition

Conditional probability measures the likelihood of an event given that another event has occurred. Example:

  • Event A: Drawing a red card from a deck.
  • Event B: Drawing a king.
  • .

2.2 Multiplication Rule

The probability of both and occurring: Worked Example: Problem: A bag has 3 red and 2 blue balls. Two balls are drawn without replacement. What is the probability both are red? Solution:

  1. .
  2. .
  3. .

2.3 Independent Events

Two events and are independent if: Implication: and . Example:

  • Flipping a coin twice: , .
  • . Independent.

Non-Example:

  • Drawing two cards without replacement from a deck: . Dependent.

3. Bayes’ Theorem

3.1 Statement

Bayes’ Theorem relates conditional probabilities and is used to "reverse" probabilities: Where:

  • : Likelihood of given .
  • : Prior probability of .
  • : Total probability of (can be expanded using the Law of Total Probability).

3.2 Law of Total Probability

For mutually exclusive and exhaustive events : Worked Example: Problem: A disease affects 1% of a population. A test is 95% accurate (95% true positive, 95% true negative). If a randomly selected person tests positive, what is the probability they have the disease? Solution:

  1. Define:
    • : Disease present ().
    • : Disease absent ().
    • : Test positive.
  2. Given:
    • (true positive rate).
    • ⇒ (false positive rate).
  3. Apply Bayes’ Theorem:
  4. Calculate using the Law of Total Probability:
  5. Final probability: Interpretation: Even with a positive test, there’s only a 16.1% chance the person has the disease due to the low prior probability.

4. Applications of Conditional Probability

4.1 Real-World Scenarios

Application Example Key Formula Used
Medical Testing Calculating false positives/negatives in disease screening. Bayes’ Theorem
Spam Filtering Probability an email is spam given certain keywords.
Quality Control Probability a product is defective given a failed inspection.
Cryptography Probability a cipher is broken given a partial key. Conditional probability chains
Finance Probability a stock price drops given economic indicators.

4.2 Combinatorial Problems

Worked Example (from past exams): Problem: You have 9 families to invite to a wedding but can only invite 6. How many different sets of invitations can you write? Solution:

  • This is a combinatorial probability problem if we consider probabilities (e.g., "What’s the chance a specific family is invited?").
  • Total ways to choose 6 out of 9: .
  • If probabilities are involved (e.g., "What’s the probability Family A is invited?"), use: (Since if Family A is invited, we choose 5 more from the remaining 8.)

5. Common Mistakes and Pitfalls

  1. Ignoring Sample Space:

    • Mistake: Calculating without defining .
    • Fix: Always state the total number of possible outcomes.
  2. Misapplying Independence:

    • Mistake: Assuming events are independent when they are not (e.g., drawing cards without replacement).
    • Fix: Use the multiplication rule .
  3. Confusing and :

    • Mistake: Reversing the condition (e.g., using when is needed).
    • Fix: Draw a probability tree or use Bayes’ Theorem.
  4. Forgetting Mutually Exclusivity:

    • Mistake: Adding probabilities of non-mutually exclusive events without subtracting .
    • Fix: Use .
  5. Incorrect Use of Combinations:

    • Mistake: Using permutations when order doesn’t matter (or vice versa).
    • Fix: Recall for combinations.

6. Exam Tip: How to Score Full Marks

6.1 Understanding the Question

  • Key Phrases:
    • "Given that..." → Conditional probability .
    • "Probability of both..." → Multiplication rule .
    • "At least one..." → Use complement rule .

6.2 Step-by-Step Solutions

  1. Define Events Clearly:
    • Label all events (e.g., ) and their complements.
  2. Draw a Diagram:
    • Use Venn diagrams for overlapping events or probability trees for conditional problems.
  3. Apply the Correct Formula:
    • For Bayes’ Theorem, always write: and expand using the Law of Total Probability.
  4. Show All Calculations:
    • Partial credit is given for correct intermediate steps. For example:
      • Calculate separately.
      • Expand explicitly.
  5. Check Units and Logic:
    • Ensure probabilities are between 0 and 1.
    • Verify if the answer makes intuitive sense (e.g., a 90% chance of a rare disease testing positive should seem low).

6.3 Common Exam Questions and Strategies

Question Type Strategy Example
Basic Probability Use . "Probability of rolling an even number."
Conditional Probability Identify and use . "Probability of rain given humidity > 80%."
Bayes’ Theorem Write all priors, likelihoods, and use . Medical testing problems.
Independence Check if . "Are two coin flips independent?"
Combinatorial Probability Use or . "Probability of picking 2 aces from a deck."

6.4 Practice Problems for TU Exams

  1. Problem: A box contains 5 red, 3 blue, and 2 green balls. Two balls are drawn with replacement. What is the probability both are blue? Solution: Since independent:

  2. Problem: In a class, 60% pass Math, 70% pass Science, and 50% pass both. What is the probability a student passes at least one subject? Solution: Use the inclusion-exclusion principle:

  3. Problem: A factory produces 10% defective items. A test detects 90% of defects but has a 5% false positive rate. What is the probability an item is defective given it tested positive? Solution: Apply Bayes’ Theorem:

    • , .
    • , .
    • .

7. Summary Table: Key Formulas

Concept Formula When to Use
Probability of an Event Basic probability calculations.
Complement Rule Finding "not E" probabilities.
Addition Rule Probability of either E or F occurring.
Multiplication Rule Probability of both E and F occurring.
Conditional Probability Probability of E given F has occurred.
Bayes’ Theorem Reversing conditional probabilities.
Independence Checking if two events are independent.
Law of Total Probability Expanding for Bayes’ Theorem.

8. Final Notes

  • Memorize: The definitions of sample space, events, and the three probability axioms.
  • Practice: Work through problems involving with/without replacement, with/without order, and dependent/independent events.
  • Bayes’ Theorem: This is a high-weight topic in TU exams. Master it by solving medical testing and spam filter problems.
  • Combinatorics Link: Probability often combines with counting principles (e.g., ). Review permutations/combinations if needed.
  • Real-World Connection: Relate problems to scenarios like risk assessment, machine learning (Naive Bayes), or game theory.

Exam Tip:

  • Time Management: Probability questions in TU exams often carry 5–10 marks. Spend ~5 minutes defining events and ~5 minutes calculating.
  • Show Work: Even if you struggle, partial credit is given for correct steps. For example:
    • Writing earns marks.
    • Expanding using the Law of Total Probability earns additional marks.
  • Avoid Assumptions: If a problem doesn’t specify replacement, assume no replacement (dependent events). If it’s ambiguous, state your assumption.

Based on the TU BSc CSIT syllabus for Discrete Structure (CSC165), unit 11.

Discussion

Loading…