🧩Discrete Mathematics Unit 7 – Counting and Probability

Key Concepts and Definitions

• Probability measures the likelihood of an event occurring and ranges from 0 (impossible) to 1 (certain)
• Sample space ($S$) represents the set of all possible outcomes of an experiment or random process
  • Example: Rolling a fair six-sided die has a sample space of $S = \{1, 2, 3, 4, 5, 6\}$
• An event is a subset of the sample space and consists of one or more outcomes
• The complement of an event $A$, denoted as $A'$ or $\bar{A}$, includes all outcomes in the sample space that are not in $A$
• Mutually exclusive events cannot occur simultaneously in a single trial (e.g., rolling a 1 and a 6 on a single die roll)
• Independent events do not influence each other's probability (e.g., consecutive coin flips)
• A random variable is a function that assigns a numerical value to each outcome in a sample space

Counting Principles

• The fundamental counting principle states that if an event can occur in $m$ ways and another independent event can occur in $n$ ways, then the two events can occur together in $m \times n$ ways
• The sum rule states that if an event can occur in $m$ ways or $n$ ways, where the two sets of outcomes are mutually exclusive, then the event can occur in $m + n$ ways
• The product rule states that if an event can occur in $m$ ways and another event can occur in $n$ ways after the first event has occurred, then the two events can occur in sequence in $m \times n$ ways
• The pigeonhole principle asserts that if $n$ items are placed into $m$ containers and $n > m$, then at least one container must contain more than one item
• Permutations and combinations are powerful tools for counting the number of ways to arrange or select items from a set

Permutations and Combinations

• A permutation is an ordered arrangement of distinct objects
  • The number of permutations of $n$ distinct objects is given by $n!$ (n factorial)
• A combination is an unordered selection of objects from a set
  • The number of combinations of $n$ objects taken $r$ at a time is denoted as $\binom{n}{r}$ or $C(n, r)$ and is calculated using the formula: $\binom{n}{r} = \frac{n!}{r!(n-r)!}$
• Permutations with repetition occur when objects can be repeated in the arrangement
  • The number of permutations of $n$ objects with repetition, taken $r$ at a time, is $n^r$
• Combinations with repetition occur when objects can be repeated in the selection
  • The number of combinations of $n$ objects with repetition, taken $r$ at a time, is $\binom{n+r-1}{r}$

Probability Basics

• The probability of an event $A$, denoted as $P(A)$, is the number of favorable outcomes divided by the total number of possible outcomes in the sample space
• For a discrete random variable $X$, the probability mass function (PMF) gives the probability of each possible value of $X$
• The cumulative distribution function (CDF) of a random variable $X$, denoted as $F(x)$, gives the probability that $X$ takes a value less than or equal to $x$
• The expected value (or mean) of a discrete random variable $X$, denoted as $E(X)$, is the sum of each possible value multiplied by its probability: $E(X) = \sum_{x} x \cdot P(X = x)$
• The variance of a discrete random variable $X$, denoted as $Var(X)$, measures the spread of the distribution and is given by: $Var(X) = E(X^2) - [E(X)]^2$
• The standard deviation is the square root of the variance and has the same units as the random variable

Conditional Probability

• Conditional probability measures the probability of an event $A$ occurring given that another event $B$ has already occurred, denoted as $P(A|B)$
• The formula for conditional probability is: $P(A|B) = \frac{P(A \cap B)}{P(B)}$, where $P(A \cap B)$ is the probability of both events $A$ and $B$ occurring
• Two events $A$ and $B$ are independent if and only if $P(A|B) = P(A)$ or $P(B|A) = P(B)$
• The multiplication rule for conditional probability states that $P(A \cap B) = P(A) \cdot P(B|A)$
• Bayes' theorem relates conditional probabilities and is given by: $P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$
  • It is often used to update probabilities based on new information

Probability Distributions

• A probability distribution is a function that describes the likelihood of different outcomes in a random experiment
• Discrete probability distributions have a countable number of possible outcomes (e.g., binomial, Poisson, geometric)
  • The binomial distribution models the number of successes in a fixed number of independent trials with a constant probability of success
  • The Poisson distribution models the number of rare events occurring in a fixed interval of time or space
• Continuous probability distributions have an uncountable number of possible outcomes (e.g., normal, exponential, uniform)
  • The normal (or Gaussian) distribution is a symmetric, bell-shaped curve characterized by its mean and standard deviation
  • The exponential distribution models the time between events in a Poisson process
• The joint probability distribution of two or more random variables gives the probability of each combination of values

Applications in Computer Science

• Counting principles and probability are essential in algorithm analysis and complexity theory
  • For example, the number of possible permutations of a list is a factor in the time complexity of sorting algorithms
• Randomized algorithms use probability to make decisions, often leading to simpler, faster, or more efficient solutions than deterministic algorithms
  • Examples include quicksort, primality testing, and skip lists
• Probabilistic data structures, such as Bloom filters and count-min sketches, use probability to represent large datasets with reduced memory requirements, at the cost of a small error rate
• Machine learning and data science heavily rely on probability theory for tasks such as classification, clustering, and Bayesian inference
• Cryptography uses probability to analyze the security of encryption schemes and the hardness of computational problems

Common Pitfalls and Tips

• When solving counting problems, be careful not to overcount or undercount the number of possibilities
  • Consider whether order matters (permutations) or not (combinations) and whether repetition is allowed
• In probability calculations, make sure to use the correct sample space and event definitions
  • Clearly identify the assumptions and conditions of the problem
• Remember that probability is always between 0 and 1, inclusive
  • If a calculated probability is negative or greater than 1, there is likely an error in the solution
• When working with conditional probability, be mindful of the direction of the conditioning and the difference between $P(A|B)$ and $P(B|A)$
• In Bayes' theorem, make sure to use the correct prior and likelihood probabilities
• When applying probability distributions, verify that the assumptions of the distribution are met by the problem scenario
  • For example, the binomial distribution requires independent trials with a constant probability of success