Lecture Notes on Probability, Counting, and Common Sense

General Comments on Homework

• Common Sense

  • Use common sense in homework answers.
  • Results may defy intuition but don’t abandon reasoning.
  • Calculators are allowed for homework but not necessary for exams.
  • Simplify obvious calculations (e.g., 4/2 = 2).

• Special Cases & Checking Answers

  • Check answers using different approaches.
  • Validate using simple and extreme cases (e.g., plug in special values).
  • Use multiple methods to confirm answers.

• Labeling

  • Label groups for clarity (e.g., number people or items).
  • Especially useful in probability and counting problems.
  • Supports self-annotation (e.g., 52 choose 5 = choosing 5 out of 52).

Counting Principles

• Choosing Teams Example

  • Split 10 people into teams: 10 choose 4 = 10 choose 6.
  • Distinction between groups affects calculations (e.g., team A vs. team B).
  • For indistinguishable teams, divide by the number of arrangements.

• Naive Definition of Probability

  • Assumes equally likely outcomes.
  • Be wary of breaking problems into unequally likely events.
  • Use naive definition under correct assumptions.

Sampling Table Discussion

• Sampling with Replacement, Order Matters

  • Focused on counting ways with replacement, ignoring order.
  • Formula: n + k - 1 choose k.
  • Check cases: k=0, k=1, n=2 for intuition.

• Indistinguishable Particles

  • Important concept in physics and counting.
  • Distinguish between obvious labeling and indistinguishable concepts.

Story Proofs and Counting Identities

• Story Proofs

  • Use real-world interpretations for proofs (e.g., committee and president).
  • Helps understand identities without algebra.

• Vandermonde's Identity

  • m + n choose k expressed as a sum.
  • Use group selection logic to prove using stories.

Advanced Probability

• Non-Naive Probability

  • Definition requires probability spaces (S, sample space; P, probability function).
  • P is a function from events to [0, 1].

• Axioms of Probability

  • Axiom 1: P(empty set) = 0, P(full space) = 1.
  • Axiom 2: P(union of disjoint events) = sum of probabilities.

Important Concepts

• Sample Space

  • Set of all possible outcomes.
  • S = {all outcomes of an experiment}.

• Events

  • Subsets of the sample space.
  • Probability defined over events.