📊 Random Variables, Expectation & Variance
Why it matters: Expected values (often via indicator variables), variance rules and density questions appear in many papers, including inside algorithms questions.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.
1Random variables: PMF, PDF and CDF
2Continuous random variables: normalising a density
3Expectation and E[g(X)]
4Linearity of expectation and indicator variables
5Variance and standard deviation
6Markov and Chebyshev inequalities
Formulas
PMF / density
Σ p(x) = 1; ∫ f(x) dx = 1; P(a ≤ X ≤ b) = ∫ₐᵇ f
CDF
F(x) = P(X ≤ x), non-decreasing from 0 to 1; P(a < X ≤ b) = F(b) − F(a)
Expectation
E[X] = Σ x p(x) = ∫ x f(x) dx; E[g(X)] = Σ g(x) p(x)
Linearity
E[aX + bY + c] = aE[X] + bE[Y] + c (always)
Indicator trick
X = Σ Iᵢ ⇒ E[X] = Σ P(Iᵢ = 1)
Variance
Var X = E[X²] − E[X]²; Var(aX + b) = a² Var X
Independent sum
Var(X + Y) = Var X + Var Y (add 2Cov(X, Y) if dependent)
Markov / Chebyshev
P(X ≥ a) ≤ E[X]/a; P(|X − μ| ≥ kσ) ≤ 1/k²
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
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.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
11 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
11 questions · 0 correct of 0 attempted · marks 0 / 15
Year:
GATE 2025 CS1 · Q58NAT2 marks
Consider a probability distribution given by the density function P(x). P(x) = Cx2 for 1 ≤ x ≤ 4, and 0 for x < 1 or x > 4. The probability that x lies between 2 and 3, i.e., P(2 ≤ x ≤ 3) is ______. (rounded off to three decimal places)
GATE 2025 CS2 · Q65NAT2 marks
The unit interval (0, 1) is divided at a point chosen uniformly distributed over (0, 1) in ℝ into two disjoint subintervals. The expected length of the subinterval that contains 0.4 is ______. (rounded off to two decimal places)
GATE 2022 · Q16MCQ1 mark
Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?
GATE 2021 Set 2 · Q29MCQ2 marks
In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted. If the first question is answered wrong, the student gets zero marks. If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question. If both the questions are answered correctly, the student gets the sum of the marks of the two questions. The following table shows the probability of correctly answering a question and the marks of the question respectively: QuesA 0.8, 10 marks; QuesB 0.5, 20 marks. Assuming that the student always wants to maximize her expected marks in the examination, in which order should she attempt the questions and what is the expected marks for that order (assume that the questions are independent)?
GATE 2019 Set 2 · Q46NAT2 marks
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ______.
GATE 2017 Set 1 · Q19NAT1 mark
Let X be a Gaussian random variable with mean 0 and variance σ2. Let Y = max(X, 0) where max(a, b) is the maximum of a and b. The median of Y is ______.
GATE 2016 Set 1 · Q4NAT1 mark
A probability density function on the interval [a, 1] is given by 1/x2 and outside this interval the value of the function is zero. The value of a is ______.
GATE 2014 Set 1 · Q2NAT1 mark
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ______.
GATE 2014 Set 2 · Q2NAT1 mark
Each of the nine words in the sentence "The quick brown fox jumps over the lazy dog" is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is ______. (The answer should be rounded to one decimal place.)
GATE 2013 Code A · Q24MCQ1 mark
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
GATE 2012 Code A · Q21MCQ1 mark
Consider a random variable X that takes values +1 and −1 with probability 0.5 each. The values of the cumulative distribution function F(x) at x = −1 and +1 are
Common traps
E[X²] ≠ E[X]²; the difference is the variance (and it is never negative).
Linearity needs no independence, but Var(X + Y) = Var X + Var Y does.
Var(aX + b) = a² Var X: the shift b drops out, the scale is squared.
A density can exceed 1 at a point; only its integral must be 1.
The CDF of a discrete variable includes the mass at the point: F(−1) = P(X ≤ −1), not P(X < −1).