Short notes: Probability & Statistics
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
The most frequent type in every paper: dice, coins, bags, random numbers and "at least one". Mostly counting plus one rule (complement or inclusion-exclusion).
- Sample space, events and equally likely outcomes. A sample space Ω lists every possible outcome; an event is a subset of it. If all outcomes are equally likely, P(E) = |E| / |Ω|. Probabilities are between 0 and 1 and P(Ω) = 1. Always state what an outcome is (ordered pair of dice, or only the sum?) before counting.→ P(E) = favourable / total, but only when you count equally likely outcomes (use ordered pairs for dice).
- Counting for probability: dice, cards, bags. Count favourable and total outcomes with products (independent steps) and combinations C(n, k) (unordered choices). Drawing k items without replacement from N: total C(N, k). With replacement: Nk ordered outcomes. "At least one" is easiest as 1 − P(none).→ Count with C(n, k) for unordered picks and products for independent steps; "at least one" is 1 − P(none).
- Union, complement and inclusion-exclusion. P(A ∪ B) = P(A) + P(B) − P(A ∩ B). P(Aᶜ) = 1 − P(A). P(A ∩ Bᶜ) = P(A) − P(A ∩ B). De Morgan: P(Aᶜ ∩ Bᶜ) = 1 − P(A ∪ B). For three events add the pairwise intersections back in with a minus sign and the triple one with a plus.→ P(A ∪ B) = P(A) + P(B) − P(A ∩ B); "neither" = 1 − P(A ∪ B).
- Mutually exclusive vs independent events. Mutually exclusive: A ∩ B = ∅, so P(A ∩ B) = 0 and P(A ∪ B) = P(A) + P(B). Independent: P(A ∩ B) = P(A)P(B). They are different ideas: two exclusive events with non-zero probability are dependent (if A happens then B certainly did not).→ Exclusive: P(A ∩ B) = 0. Independent: P(A ∩ B) = P(A)P(B). With positive probabilities they exclude each other.
- Repeated trials and "retry until decided" experiments. If an experiment is repeated until it ends in a decisive result, tie/retry rounds just restart it. With per-round probabilities a (outcome Y), b (outcome N) and c (retry), P(final = Y) = a/(a + b) and the round that decides is geometric: P(decided in round k) = ck−1(1 − c). For "wins on the k-th trial", multiply k − 1 retries by one decisive round.→ For retry experiments, P(Y) = a/(a + b); the deciding round is geometric.
Formulas
What GATE asks
- ★★★Probability with dice, coins, bags or random numbers. Define the outcome space, count favourable cases, or use 1 − P(none). Often appears in General Aptitude too.
- ★★★Union / complement with given P(A), P(B), P(A ∩ B). Use inclusion-exclusion and De Morgan; test independence with the product rule.
- ★★★Random choice inside another topic (quicksort pivot, relations, hashing). Count the good choices among all equally likely choices: 2/25 for a worst pivot, 2⁶/2⁹ for a reflexive relation.
- ★★★Repeat-until-decided experiments. Ignore the retries (condition on a decisive round) or sum a geometric series.
Traps
Bayes with a table or two-step experiment appears nearly every year, and independence statements are a favourite true/false item.
- Conditional probability and the multiplication rule. P(A | B) = P(A ∩ B) / P(B) (for P(B) > 0): the probability of A once you know B happened, i.e. B becomes the new sample space. Rearranged, the multiplication rule: P(A ∩ B) = P(B) P(A | B). For a chain of draws: P(A ∩ B ∩ C) = P(A) P(B | A) P(C | A ∩ B).→ P(A | B) = P(A ∩ B)/P(B); condition by shrinking the sample space and updating the counts.
- Law of total probability. If B₁, ..., Bₙ partition the sample space (disjoint, covering everything), then P(A) = Σ P(Bᵢ) P(A | Bᵢ). Use it when the experiment has a first stage that changes the probabilities of the second: "pick a coin, then toss", "first draw, then second draw".→ Total probability: P(A) = Σ P(Bᵢ) P(A | Bᵢ).
- Bayes' theorem. P(Bᵢ | A) = P(Bᵢ) P(A | Bᵢ) / Σⱼ P(Bⱼ) P(A | Bⱼ). It turns "probability of the evidence given each cause" into "probability of each cause given the evidence". Recipe: list the hypotheses with their priors, multiply by the likelihoods to get joints, add them for P(evidence), and divide.→ Posterior = prior × likelihood, divided by the sum over all causes.
- Independence of events (pairwise vs mutual). A and B are independent if P(A ∩ B) = P(A)P(B), equivalently P(A | B) = P(A). For three or more events, mutual independence needs the product rule for every sub-collection, including the triple; pairwise independence only needs it for pairs and is weaker.→ Independent ⇔ P(A ∩ B) = P(A)P(B); mutual independence needs every sub-collection, pairwise is weaker.
Formulas
What GATE asks
- ★★★Bayes' theorem with a table or a two-stage experiment. Posterior = joint / total. Fake coin, suppliers, signal and receiver, weather tables.
- ★★★Total probability of an event across cases. Weighted average of the conditional probabilities (shop with two bulb types, urn changes after a draw).
- ★★★Which statements about independence are true?. Compute P(A ∩ B) and compare with P(A)P(B); symmetry arguments for random permutations.
- ★★★Draws with changes after each draw. Condition on the first draw (green removed, orange replaced) and use total probability.
Traps
Expected values (often via indicator variables), variance rules and density questions appear in many papers, including inside algorithms questions.
- Random variables: PMF, PDF and CDF. A random variable X assigns a number to each outcome. Discrete: the PMF p(x) = P(X = x) with Σ p(x) = 1. Continuous: a density f(x) ≥ 0 with ∫ f = 1 and P(a ≤ X ≤ b) = ∫ₐᵇ f(x) dx (single points have probability 0). The CDF F(x) = P(X ≤ x) rises from 0 to 1; for a discrete X it includes the mass at x itself.→ PMF values add to 1; F(x) = P(X ≤ x) is a non-decreasing step function that includes the mass at x.
- Continuous random variables: normalising a density. To use an unknown constant C in a density, impose ∫ f(x) dx = 1 over its support. Then P(a ≤ X ≤ b) is the area between a and b, E[X] = ∫ x f(x) dx, and F(x) = ∫ f up to x. For the uniform density the area is just a length times the constant height.→ Normalise the density to total area 1, then integrate over the asked range.
- Expectation and E[g(X)]. E[X] = Σ x p(x) (or ∫ x f(x) dx): the long-run average. For a function, E[g(X)] = Σ g(x) p(x): apply g to the values, not to the mean. In general E[g(X)] ≠ g(E[X]) (only for linear g). Also E[X] = Σ P(X > k) for a non-negative integer-valued X.→ E[X] = Σ x p(x); E[g(X)] = Σ g(x) p(x), never g(E[X]) unless g is linear.
- Linearity of expectation and indicator variables. E[X + Y] = E[X] + E[Y] always, independent or not. To count something that is a sum of yes/no events, write X = ΣIᵢ with indicators and use E[X] = ΣP(Iᵢ = 1): fixed points of a random permutation, empty bins, triangles in a random graph, keys per hash slot (n/m).→ E[ΣIᵢ] = ΣP(Iᵢ = 1); linearity needs no independence.
- Variance and standard deviation. Var(X) = E[X²] − (E[X])² = E[(X − μ)²]. Var(aX + b) = a² Var(X). For independent X, Y: Var(X + Y) = Var X + Var Y (in general add 2 Cov). Standard deviation σ = √Var has the units of X.→ Var X = E[X²] − E[X]²; Var(aX + b) = a² Var X.
- Markov and Chebyshev inequalities. Markov (X ≥ 0): P(X ≥ a) ≤ E[X]/a. Chebyshev: P(|X − μ| ≥ kσ) ≤ 1/k², for any distribution with finite variance. They give guaranteed (usually loose) bounds when you know only the mean (and variance).→ Markov: P(X ≥ a) ≤ E[X]/a for X ≥ 0. Chebyshev: P(|X − μ| ≥ kσ) ≤ 1/k².
Formulas
What GATE asks
- ★★★Expected value by indicators / uniform choice. Expected keys per slot n/m, expected triangles C(n,3)/8, expected distance between random leaves, expected piece length.
- ★★★Find the constant or a probability for a density. Normalise to 1, then integrate over the asked range.
- ★★★CDF values and median of a function of a variable. F(x) includes the point mass; median of max(X, 0) is 0 when P(X ≤ 0) = 1/2.
- ★★★Compare orderings by expected value. Compute the expected marks of each order and pick the larger.
Traps
Direct formula questions: mean and variance of a binomial or Poisson, the exponential tail, uniform intervals, normal z-scores.
- Uniform distribution. Discrete uniform on {1..n}: every value 1/n, mean (n + 1)/2, variance (n² − 1)/12. Continuous uniform on [a, b]: density 1/(b − a), mean (a + b)/2, variance (b − a)²/12. P(c ≤ X ≤ d) = (d − c)/(b − a): just a ratio of lengths.→ Uniform: probability = length ratio; mean (a + b)/2, variance (b − a)²/12.
- Bernoulli and binomial. Bernoulli(p): one trial, mean p, variance p(1 − p). Binomial(n, p): number of successes in n independent trials, P(k) = C(n, k) pᵏ (1 − p)ⁿ⁻ᵏ, mean np, variance np(1 − p). The most likely value (mode) is near (n + 1)p.→ Binomial(n, p): C(n, k)pᵏ(1 − p)ⁿ⁻ᵏ, mean np, variance np(1 − p).
- Geometric distribution. Number of trials until the first success: P(X = k) = (1 − p)ᵏ⁻¹ p, k = 1, 2, ...; mean 1/p, variance (1 − p)/p². It is memoryless: P(X > m + n | X > m) = P(X > n). Expected number of rolls for a six: 6.→ Geometric: P(k) = (1 − p)^(k−1)p, mean 1/p, memoryless.
- Poisson distribution. Counts of rare independent events in a fixed interval at average rate λ: P(k) = e⁻λ λᵏ / k!. Mean = variance = λ, so E[X²] = λ + λ². Sums of independent Poissons are Poisson with the rates added. It approximates Binomial(n, p) for large n and small p (λ = np).→ Poisson(λ): P(k) = e⁻λλᵏ/k!, mean = variance = λ.
- Exponential distribution. Waiting time between Poisson events at rate λ: density λe⁻λx (x ≥ 0), P(X > t) = e⁻λt, mean 1/λ, variance 1/λ². Memoryless. P(X > mean) = e⁻¹ ≈ 0.368 whatever λ is.→ Exponential(λ): P(X > t) = e^(−λt), mean 1/λ, memoryless.
- Normal distribution and z-scores. The bell curve N(μ, σ²) is symmetric about μ. Standardise: Z = (X − μ)/σ ~ N(0, 1), then look up Φ(z). About 68% / 95% / 99.7% lie within 1 / 2 / 3 standard deviations. A sum of independent normals is normal (means add, variances add).→ Standardise: z = (x − μ)/σ; 68–95–99.7 within 1, 2, 3 standard deviations.
Formulas
What GATE asks
- ★★★Mean, variance or standard deviation of a named distribution. Binomial np(1 − p) (e.g. 1000 tosses at 0.4 gives √240), Poisson mean = variance.
- ★★★Probability from the Poisson or exponential formula. Sum a few Poisson terms; P(X > mean) for the exponential is 1/e.
- ★★★Uniform random parameter in an inequality. Solve the condition for the variable, then take a length ratio.
- ★★★Independent trials all succeed / most likely count. Use p^n for all-succeed; for the most likely number of successes compare binomial terms near np.
Traps
Rare but real: Cauchy–Schwarz and covariance statements, E[XY] questions, and the law of total expectation.
- Joint and marginal distributions, independence of variables. The joint PMF p(x, y) = P(X = x, Y = y). Marginals are row and column sums: pₓ(x) = Σᵧ p(x, y). X and Y are independent iff p(x, y) = pₓ(x) pᵧ(y) for every cell, equivalently the table is the product of its margins.→ Independent ⇔ every cell = (row total) × (column total).
- Covariance and correlation. Cov(X, Y) = E[XY] − E[X]E[Y]. Independent ⇒ Cov = 0, but Cov = 0 does not imply independent. Correlation ρ = Cov/(σₓσᵧ) lies in [−1, 1]; the Cauchy–Schwarz inequality says Cov² ≤ Var X · Var Y, with equality only for an exact linear relationship. And Var(X + Y) = Var X + Var Y + 2 Cov(X, Y).→ Cov = E[XY] − E[X]E[Y]; Cov² ≤ Var X · Var Y; uncorrelated does not mean independent.
- Conditional expectation and the law of total expectation. E[X | Y = y] is the average of X among outcomes with Y = y. Law of total expectation: E[X] = Σ P(Y = y) E[X | Y = y]. It powers first-step analysis: condition on what happens first and use the fact that the process restarts (geometric mean 1/p).→ E[X] = Σ P(Y = y) E[X | Y = y]; condition on the first step and use the restart.
Formulas
What GATE asks
- ★★★True or false: covariance and variance statements. Cauchy–Schwarz kills Cov² > Var·Var; covariance has no absolute values.
- ★★★Compare E[xy] with E[x]E[y], or bound E[xy]. If y ≤ 1 and x ≥ 0 then xy ≤ x; for xy vs x̄ȳ you need the covariance sign.
Traps
Short items: median of a sample, effect of shifting or scaling a list, and the idea behind the central limit theorem.
- Mean, median and mode. Mean = sum / count. Median = middle value of the sorted list (average of the two middle values when the count is even). Mode = most frequent value (can be several, or none). The mean is pulled by outliers; the median is robust. For a symmetric distribution mean = median.→ Median = middle of the sorted list (average the two middle values for even n); the mean is sensitive to outliers.
- Variance and standard deviation of data. For data x₁..xₙ: variance = (1/n) Σ(xᵢ − x̄)² (population) or divided by n − 1 for a sample estimate. Effects on a list: adding b adds b to the mean and leaves variance and SD unchanged; multiplying by a multiplies the mean by a, the SD by |a| and the variance by a².→ Shift: mean moves, SD does not. Scale by a: SD × |a|, variance × a².
- Sampling distribution and the central limit theorem. The mean X̄ of n independent draws from a population with mean μ and standard deviation σ has mean μ and standard deviation σ/√n. By the central limit theorem, for large n X̄ is approximately normal, whatever the population looks like. More data narrows the spread by √n.→ Sample mean: mean μ, SD σ/√n, and approximately normal for large n (central limit theorem).
Formulas
What GATE asks
- ★★★Median or mean of a sample. Sort, then take the middle or the average of the middle two. Check for an outlier that makes the mean misleading.
- ★★★Effect of adding to or doubling every entry. Mean follows the transformation; SD ignores the shift and scales by |a|.