🔢Analytic Combinatorics Unit 13 – Discrete Random Variables

Key Concepts and Definitions

• Discrete random variables take on a countable number of distinct values, typically integers or natural numbers
• Sample space represents the set of all possible outcomes of a random experiment
• Events are subsets of the sample space and can be assigned probabilities
• Probability is a measure of the likelihood of an event occurring, ranging from 0 to 1
  • 0 indicates an impossible event
  • 1 indicates a certain event
• Independence means the occurrence of one event does not affect the probability of another event
• Mutual exclusivity means two events cannot occur simultaneously (disjoint sets)

Probability Mass Functions

• Probability Mass Function (PMF) denoted as $P(X = x)$ gives the probability that a discrete random variable $X$ takes on a specific value $x$
• PMF satisfies two conditions:
  1. $P(X = x) \geq 0$ for all $x$ in the domain of $X$
  2. $\sum_{x} P(X = x) = 1$, the sum of probabilities over all possible values of $X$ equals 1
• PMF fully characterizes the probability distribution of a discrete random variable
• Can be represented as a table, formula, or graph
• Allows calculation of probabilities for specific events or ranges of values

Cumulative Distribution Functions

• Cumulative Distribution Function (CDF) denoted as $F(x) = P(X \leq x)$ gives the probability that a random variable $X$ takes a value less than or equal to $x$
• CDF is non-decreasing, meaning $F(a) \leq F(b)$ if $a \leq b$
• $\lim_{x \to -\infty} F(x) = 0$ and $\lim_{x \to \infty} F(x) = 1$
• CDF can be derived from the PMF by summing probabilities: $F(x) = \sum_{t \leq x} P(X = t)$
• Probability of $X$ falling in an interval $[a, b]$ is given by $P(a \leq X \leq b) = F(b) - F(a)$
• Useful for determining percentiles and quantiles of a distribution

Expected Value and Variance

• Expected value (mean) of a discrete random variable $X$ is denoted as $E[X]$ and calculated as $E[X] = \sum_{x} x \cdot P(X = x)$
  • Represents the average value of $X$ over many trials
• Variance measures the dispersion of a random variable around its mean, denoted as $Var(X)$ or $\sigma^2$
  • Calculated as $Var(X) = E[(X - E[X])^2] = E[X^2] - (E[X])^2$
  • Standard deviation is the square root of variance, denoted as $\sigma$
• Linearity of expectation: For random variables $X$ and $Y$, $E[X + Y] = E[X] + E[Y]$
• Variance of a sum: For independent random variables $X$ and $Y$, $Var(X + Y) = Var(X) + Var(Y)$

Common Discrete Distributions

• Bernoulli distribution: Models a single trial with two possible outcomes (success with probability $p$, failure with probability $1-p$)
• Binomial distribution: Models the number of successes in a fixed number of independent Bernoulli trials
  • PMF: $P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$ for $k = 0, 1, ..., n$
• Geometric distribution: Models the number of trials until the first success in a sequence of independent Bernoulli trials
  • PMF: $P(X = k) = (1-p)^{k-1} p$ for $k = 1, 2, ...$
• Poisson distribution: Models the number of events occurring in a fixed interval of time or space, given a constant average rate
  • PMF: $P(X = k) = \frac{e^{-\lambda} \lambda^k}{k!}$ for $k = 0, 1, 2, ...$
• Hypergeometric distribution: Models the number of successes in a fixed number of draws from a finite population without replacement

Generating Functions for Discrete Random Variables

• Generating functions encode information about the probability distribution of a discrete random variable
• Probability Generating Function (PGF) of a discrete random variable $X$ is defined as $G_X(z) = E[z^X] = \sum_{k=0}^{\infty} P(X = k) z^k$
  • Coefficients of the PGF correspond to the probabilities of $X$ taking on specific values
• Moment Generating Function (MGF) of a discrete random variable $X$ is defined as $M_X(t) = E[e^{tX}] = \sum_{k=0}^{\infty} P(X = k) e^{tk}$
  • Derivatives of the MGF evaluated at $t=0$ give the moments of the distribution
• Generating functions facilitate the derivation of properties and calculations involving discrete random variables
  • Convolution of independent random variables corresponds to the product of their generating functions
• Useful for analyzing combinatorial structures and deriving asymptotic properties

Applications in Combinatorial Problems

• Discrete random variables naturally arise in combinatorial problems
• Occupancy problems: Distributing balls into urns
  • Number of empty urns, urns with exactly $k$ balls, or maximum number of balls in any urn
• Hashing and load balancing: Analyzing the distribution of keys among hash table buckets
• Random graphs and networks: Degree distribution, connectivity, and component sizes
• Randomized algorithms: Analyzing the performance and correctness of algorithms that make random choices
• Queueing theory: Modeling the number of customers in a queue or the waiting time distribution

Advanced Topics and Extensions

• Multivariate discrete distributions: Joint probability mass functions, marginal and conditional distributions
• Discrete stochastic processes: Sequences of discrete random variables indexed by time (Markov chains, random walks)
• Discrete-time martingales: Sequences of random variables with conditional expectation equal to the previous value
• Concentration inequalities for discrete random variables: Bounds on the deviation of a random variable from its expected value (Chernoff bounds, Hoeffding's inequality)
• Discrete entropy and information theory: Measuring the uncertainty or information content of a discrete random variable
• Discrete probabilistic methods in combinatorics: Probabilistic existence proofs, second moment method, Lovász Local Lemma
• Discrete choice models: Modeling and analyzing decision-making processes with discrete alternatives (logit, probit models)