Probability · Lesson 9 of 9
The hard problems
The Delhi School of Economics entrance sets the hardest probability questions of any Indian economics exam, often harder than today’s papers need. They reward a handful of techniques rather than new formulas. This lesson teaches those techniques, then gives you every DSE question above the easy level, 114 in all, in five sets.
A question to hold on to
A and B play a round; the winner plays C while the loser sits out; each winner then plays whoever sat out. The first player to win two rounds in a row wins the contest, and every round is 50–50. What is the probability that A wins? That C wins?
Delhi School of Economics entrance, 2006Solved at the end ↓
Before any formula
How to attack a hard question
A hard DSE question rarely needs mathematics beyond Lessons 1 to 7. What makes it hard is that the method is not announced. Five moves crack almost all of them; ask which one the question is inviting.
- Name the structure. Repeated independent trials, a finite box, a waiting time, a chain of states? Naming it usually names the distribution (Lesson 6).
- Use symmetry. The second ball is as likely to be red as the first; each of n gaps has the same average length. Symmetry often replaces a page of algebra with one line.
- Count with indicators. An expected number of anything is a sum of probabilities (Lesson 5), even when the events are dependent.
- Condition on the first step. When a process can restart, write the answer in terms of itself.
- Work backwards. When you choose as you go, solve the last decision first.
The first three were taught in earlier lessons. This lesson is about the last two, and the chains and contests they unlock.
The workhorse
Condition on the first step
Some games restart themselves: after one round, you face the same game again. Let E be the answer you want. Split on what happens first (Lesson 3’s total probability, applied to averages), and the same E appears on the right-hand side. Then solve for it.
Expectation by conditioning
The continuous version: E(Y) = ∫ E(Y | X = x) f(x) dx.
DSE 2012 · advanced
An urn has equal numbers of green and red balls. Draw with replacement: each green earns ₹1; the first red costs ₹1 and ends the game. What is your expected income?
- Split on the first draw.Green (½): you gain 1 and then face the same game again, worth E. Red (½): you lose 1 and stop.
- Write E in terms of itself.
- Solve.E = ½E gives E = 0.
Answer
Zero. The same method gives the mean of a geometric distribution: E = 1 + (1 − p)E, so E = 1/p.
DSE 2014 · advanced
Ms A picks X uniformly from [0, 1]. Mr B then draws independent uniforms from [0, 1] until one exceeds X/2. What is the expected number of draws?
- Fix X = x first.Each draw beats x/2 with probability 1 − x/2, so the count is geometric: E(N | x) = 1/(1 − x/2) = 2/(2 − x).
- Average over x.
Answer
2 ln 2 ≈ 1.39. The next question asked for the expected sum of B’s draws given x: the number of draws times the average draw, 2/(2 − x) × ½ = 1/(2 − x). That multiplication is justified by Wald’s identity, because the decision to stop depends only on draws already made.
Solving the opening question
The three-player contest
Tournament questions look like they need an infinite tree. The trick is to track one thing: who won the last round. Each round the current winner is challenged by the player who sat out, and the contest ends the first time a winner repeats.
The opening question · DSE 2006
A and B play first; the winner meets C; the winner always plays whoever sat out; two wins in a row takes the contest. P(A wins)? P(C wins)?
- Suppose A wins round 1.If the contest keeps going, each round’s winner is the newcomer, so the winners run A, C, B, A, C, B, … The contest ends at round k + 1 when the round-k winner wins again, and each extra round has probability ½.
- Add up the chances for each player.A takes it at rounds 2, 5, 8, …: ½ + ⅛·½ + ⋯ = (½)/(1 − ⅛) = 4/7. C at rounds 3, 6, …: (¼)/(⅞) = 2/7. B at rounds 4, 7, …: (⅛)/(⅞) = 1/7.
- Average over who wins round 1.If B wins round 1, swap A and B. So P(A) = ½(4/7 + 1/7) = 5/14, and P(C) = 2/7 either way.
Answer
P(A) = P(B) = 5/14, and P(C) = 2/7: sitting out the first round costs C. The chance that the contest is still going after n rounds is (½)ⁿ⁻¹, which tends to 0 (the third question in the set).
Interactive
Markov chains and random walks
A Markov chain moves between states, and the chance of the next state depends only on the current one, not on how you got there. Write the transition probabilities in a table P, where P(i → j) is the chance of moving from i to j. Then the distribution one step later is the current one pushed through the table: Lesson 3’s total probability, applied once per step.
One step of a Markov chain
Repeat it t times to get the distribution at time t.
A poor parent has a poor child with probability 0.7; a rich parent has a poor child with probability 0.6. Start with a poor man.
| t | Poor | Rich |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0.7000 | 0.3000 |
| 2 | 0.6700 | 0.3300 |
| 3 | 0.6670 | 0.3330 |
| 4 | 0.6667 | 0.3333 |
DSE 2014 · advanced
A poor parent’s child is poor with probability 0.7; a rich parent’s child is poor with probability 0.6. What is the chance that a poor man’s great-grandson is poor?
- Son.P(poor) = 0.7.
- Grandson: total probability.0.7 × 0.7 + 0.3 × 0.6 = 0.49 + 0.18 = 0.67.
- Great-grandson: once more.0.67 × 0.7 + 0.33 × 0.6 = 0.469 + 0.198 = 0.667.
Answer
0.667, which the options give as 0.67. It barely moves between generations because the chain is already near its long-run share of poor households, p with p = 0.7p + 0.6(1 − p), so p = 2/3. Step the lab to t = 12 to watch it settle there.
DSE 2016 · advanced
Mr Walker moves round the square A–B–C–D, each period to one of the two neighbouring corners with probability ½. He starts at A. Where is he at t = 10, and what is the chance he has not returned to A by then?
- Parity decides the position.Every step switches between the pair {A, C} and the pair {B, D}. After an even number of steps he is at A or C, each with probability ½ by symmetry.
- Avoiding A: count the risky steps.Step 1 always leaves A. From B or D, the next step goes to A or C, each with probability ½; from C both neighbours are safe. So every second step is a coin toss for survival: steps 2, 4, 6, 8 and 10.
Answer
P(A, B, C, D) at t = 10 = (½, 0, ½, 0), and P(never back at A) = (½)⁵. Pick “Walk round a square” in the lab to check both, then try the variation where he may stay put: the parity breaks and the distribution settles at ¼ each.
Negative binomial counting
Series that must end
“First to 4 wins” questions are counting questions in disguise. A series ends in game n exactly when the winner takes game n and has exactly 3 of the first n − 1.
DSE 2011 · advanced
In a best-of-seven match between equally good players, is ending in 6 games more likely, less likely, or as likely as ending in 7?
- Ends in 6.Either player wins game 6 and 3 of the first 5: 2 × C(5, 3) × (½)⁶ = 20/64 = 5/16.
- Ends in 7.Either player wins game 7 and 3 of the first 6: 2 × C(6, 3) × (½)⁷ = 40/128 = 5/16.
Answer
Equally likely: both 5/16. (Ending in 4 is 1/8 and in 5 is 1/4; the four add to 1.)
Pause and predict
The same contest as the opening question. What is the probability that it goes on for ever, with nobody winning twice in a row? (DSE 2006)
Interactive
Choosing well: allocation and stopping
Some DSE questions ask you to choose: how to set things up, or when to stop. Write the probability or the expectation as a function of your choice, then optimise it. When the choices come one after another, solve the last one first.
DSE 2011 · advanced
Put 50 red and 50 green balls into two boxes, however you like. Mr A picks a box at random and draws a ball; green admits him. What is the best chance you can give him?
- Look for a sure thing.A box holding a single green ball admits him for certain whenever he picks it: probability ½ already.
- Put everything else in the other box.49 green and 50 red: P(green) = 49/99.
- Total probability.½ × 1 + ½ × 49/99 = 0.5 + 0.2475 ≈ 0.747.
Answer
0.747. An equal split gives only 0.5; the lone green ball is worth nearly a quarter extra.
DSE 2011 · advanced
A student may sit a test up to three times; each score is uniform on [0, 100]. After a score he either keeps it or discards it and sits again, and a third score must be kept. Below what first score should he retake, to maximise his expected score?
- The last try.A third sitting is worth its average: 50.
- The second try.Keep a second score only if it beats 50. Then the second try is worth P(≥ 50) × E(score | ≥ 50) + P(< 50) × 50 = ½ × 75 + ½ × 50 = 62.5.
- The first try.Keep a first score only if it beats what the rest of the process is worth: retake below 62.5.
Answer
62.5. The expected score with this rule is about 69.5. Set other cut-offs in the lab below to see that nothing does better.
A third try is worth50.00
A second try, with your cut-off, is worth60.50
Expected official score66.20
Best possible69.53
The curve is your expected score for every first cut-off, given your second one. It peaks exactly where the cut-off equals what a retake is worth (the dashed lines cross there): keep a score if and only if it beats the value of trying again.
The rule behind every stopping problem
Stop when what you have beats the expected value of carrying on. That expected value comes from the stage after, so work from the end.
Watch out for
The mistakes examiners are fishing for
- Drawing the infinite tree. Condition on the first step, or track only the state that matters (the last winner, the current corner).
- Forgetting the answer can appear on both sides. E = ½(1 + E) − ½ is an equation to solve, not a circular argument.
- Using the average as the cut-off. The retake threshold is the value of retaking (62.5), not the mean score (50).
- Missing parity. On a square or any two-coloured board, even and odd times live on different halves.
Revise
The lesson on one screen
The lesson on one screen
- Five moves
- Name the structure, use symmetry, count with indicators, condition on the first step, work backwards.
- First-step analysis
- E = Σ P(first outcome) × E(rest | outcome); solve when E appears on both sides.
- Contests
- Track only the state that matters: in the three-player game, who won last. A and B 5/14 each, C 2/7.
- Markov chains
- Next distribution = current distribution pushed through P. Long run: solve p = pP.
- Random walks
- Check parity first. Avoiding a state multiplies the chances of each risky step.
- Series
- Ends in game n: the winner takes game n and exactly the right number of the n − 1 before it.
- Stopping
- Solve the last choice first. Keep a result if and only if it beats the value of going on.
Practice
Check yourself
Compute
Two-state chain
With the rich-and-poor chain (poor → poor 0.7, rich → poor 0.6), start from a rich man. What is the chance his grandson is poor?
Long run
A chain has two states. From state 1 it stays with probability 0.8; from state 2 it moves to state 1 with probability 0.4. What share of the time is it in state 1 in the long run?
Series
Two equal players play best of five (first to 3). What is the probability the match goes to 5 games?
First step
A fair die is rolled until a six appears. Using first-step analysis, what is the expected number of rolls?
Stopping
Up to two tries at a test, scores uniform on [0, 100]. You may keep the first score or retake, and a retaken score is final. With the best rule, what is the expected score?
Quick questions
1In a Markov chain, the probability of the next state depends on
2On the square walk (each step to a neighbour, ½ each), starting at A, P(at B after 4 steps) is
3With three tries, the student should retake after the first test if the score is below
Real questions
The DSE sets
Every Delhi School question rated moderate or harder, from the papers of 2004 to 2021, in five sets. The first four gather each earlier lesson’s hardest questions; the fifth holds the chains, contests and stopping problems of this lesson. Most students preparing for CUET-PG, JNU or JAM will not meet questions this hard. Take these sets after Lessons 1 to 7 feel routine.
Part 1 · from Lessons 1 and 2
Counting and the rules
Arrangements, geometric probability and bounds, at the Delhi School's level.
18 questionsPractise →
Part 2 · from Lessons 3 and 4
Conditioning and Bayes
Trees, total probability, independence and Bayes with a twist.
32 questionsPractise →
Part 3 · from Lesson 5
Expectation tricks
Indicators, functions of a random variable, variance of sums.
13 questionsPractise →
Part 4 · from Lessons 6 and 7
Distributions
Binomial and geometric puzzles, densities, transformations, maxima and minima.
42 questionsPractise →
Part 5 · new in this lesson
Chains, contests and stopping
Markov chains, random walks, tournaments and when to stop.
9 questionsPractise →
All 114 DSE questions, moderate before hard within each part: practise the full set →
These are questions from the TestStop bank. A free account answers 10 a day, each with its worked solution; All-Access opens every set with no daily limit.
Read next
All resources →StatisticsProbability, from zero to exam levelA module of lessons that starts at "what is a sample space" and ends at the DSE's hardest questions: counting, the rules, conditional probability, Bayes' theorem, random variables, the discrete and continuous distributions, and a final lesson of hard problems, each with its own interactives and graded past-paper sets.MicroeconomicsHow to solve a game theory questionDominant strategies, elimination, Nash by underlining, mixed strategies and backward induction, with a solver for any payoff matrix.StatisticsHypothesis testing in one placeThe 2×2 of Type I and Type II errors, power and p-values, with a lab that shows the α–β trade-off as areas.