Problems
Problems I work through, each with a full worked solution.
A coin walks a pebble through four boxes, every second toss either returning it to the start or landing it in Box 4. Each toss pair succeeds with probability 1/2, so the pair count is geometric with mean 2 and the expected wait is 4 tosses.
A 60 percent share in a 1000-person poll carries standard error sqrt(0.6 x 0.4 / 1000), about 1.5 points, so the 95 percent interval is 60 plus or minus 3. Quadrupling the sample halves the margin.
For X normal with mean 0 and variance sigma^2, completing the square gives E[e^X] = e^(sigma^2/2), the moment generating function at t = 1. The mean exceeds the median 1 because exponentiation stretches the upper tail.
Prevalence 0.5 percent, no false negatives, 7 percent false positives. Bayes prices a positive stranger at 0.005 over 0.005 + 0.07 x 0.995, about 6.7 percent, the base-rate fallacy compressed into one fraction.
Two independent uniform cuts split a unit stick into three pieces. Their ordered expected lengths are 1/9, 5/18, and 11/18, so the longest piece averages more than half the stick.
Two cards from a shuffled deck are both kings with probability (4/52)(3/51) = 1/221, about 0.45 percent, one hand in every 221.
The numbers 1 through 5 have mean 3 and summed squared deviations 10. Dividing by n = 5 gives the population value sqrt(2), dividing by n - 1 = 4 the sample value sqrt(2.5), and an honest answer names its convention.
The N(mu, sigma^2) density is e^(-(x-mu)^2 / (2 sigma^2)) over sigma sqrt(2 pi), the constant forced by the Gaussian integral, which is evaluated by squaring it and passing to polar coordinates.
Once the tosses reach HH the pattern HHT can no longer lose, so HTH must finish without ever passing through HH. The resulting chain gives HTH before HHT probability 1/3, against the apparent symmetry of the triplets.
Given corr(X,Y) = rho, both corr(X+5,Y) and corr(5X,Y) equal rho, because covariance subtracts the mean and a factor of 5 scales numerator and denominator alike.
Exit from (-a, b) via the martingale B_t^2 - t and optional stopping takes expected time ab, the product of the two barrier distances. Symmetric unit barriers make E[tau] exactly 1.
Symmetry zeroes E[B_t^3], so cov(B_t, B_t^2) = 0 and the correlation is exactly zero even though B_t^2 is a function of B_t, the standard witness that zero correlation is far weaker than independence.
For dX = dt + dW started at 0, the exponential martingale e^(-2X) with optional stopping gives P(ever reach -1) = e^(-2), about 0.135, and each further unit of depth multiplies the probability by e^(-2) again.
Four equally likely toys, one per box. The waits for each new toy are geometric with means 1, 4/3, 2, and 4, summing to 25/3, about 8.33 boxes, the final toy costing nearly as much as the first three combined.
Splitting B_2 into B_1 plus an independent increment turns the event B_1 > 0, B_2 < 0 into a quarter-plane probability at correlation 1/sqrt(2), giving 1/8, half the naive independent guess.
The expected wait for HTH is 10 flips, between THH's 8 and HHH's 14. Only the leading H survives a miss, and that single-letter self-overlap is exactly what the martingale betting argument charges for.
Brownian motion is fixed by four axioms, a zero start, independent increments, Gaussian increments of variance equal to elapsed time, and continuous paths. These force nowhere-differentiability, self-similarity, the martingale property, and quadratic variation t.
The product of two independent uniforms exceeds 1/2 on the region above the hyperbola xy = 1/2, whose area is (1 - ln 2)/2, about 0.153. The logarithm enters through the integral of 1/(2x) along the boundary.
Rejection sampling the unit d-ball from the cube [-1,1]^d succeeds with probability the volume ratio, already 0.0025 at d = 10 and 2.5 in a hundred million at d = 20, so high dimensions demand the normalised-Gaussian method instead.
Toss triplets are non-transitive, every choice beaten by the reply that prepends the complement of its middle toss. Naming second therefore wins with probability at least 2/3 under best play, and exactly 2/3 against a perfect first mover.
The expected wait for THH on a fair coin is 8 flips, against 14 for HHH. A late miss keeps THH's leading tail, so self-overlap structure, not per-position probability, sets the wait.
HHH beats THH only when the first three tosses are all heads, probability 1/8. Any earlier tail arms THH, which then must complete before any later HHH can, an absorbing argument requiring no algebra.
The expected wait for n consecutive heads on a fair coin is 2^(n+1) - 2 flips. One mistimed tail forfeits the entire run, which is why each further head roughly doubles the wait.
From metre 17 of a 100-metre bridge a symmetric one-metre walk exits the far end with probability 17/100 and takes 17 times 83 = 1411 expected steps to leave. The stopped martingale gives the exit law and the quadratic martingale gives the wait.
A wins on the first sum of 12, B on the first consecutive pair of 7s. A three-state absorption chain gives A probability 7/13, even though a 7 is six times likelier per roll, because B's pattern must survive two rolls.
The sum of n independent uniforms stays below t with probability t^n/n! for t in [0,1], proved by induction on the last draw. At t = 1 this is the volume of the standard simplex, 1/n!, vanishing factorially fast.
Open n boxes, each holding one of N equally likely coupon types. An indicator per type gives N(1 - ((N-1)/N)^n) expected distinct types, rapid gains early and a crawl once few types remain unseen.
Every box contains one of N coupon types, uniform and independent. Collecting all of them costs a sum of geometric waits, N/(N-i+1) for the ith new type, totaling N times the Nth harmonic number, with the last type alone costing an expected N boxes.
Deal a shuffled 52-card deck face up one card at a time. The four aces cut the deck into five gaps, each equally likely to hold any given non-ace, so the first ace sits at expected position 1 + 48/5 = 10.6.
For a standard normal, symmetry zeroes the odd moments and integration by parts yields the ladder E[X^n] = (n-1) E[X^(n-2)], so the fourth moment is 3, the benchmark for zero excess kurtosis.
Buses arrive by a Poisson process, one per 10 minutes on average, and you show up at a uniform random time. Memorylessness makes both the expected forward wait and the expected backward age 10 minutes, so how can the gap you stand in average 20?
Two uniform cuts on a unit stick yield a triangle exactly when no piece exceeds half the length. That condition excludes three corner triangles of the unit square of cut positions and leaves probability 1/4.
Independent constant-rate traffic leaves a 20-minute window empty with probability 16/625. A 5-minute silence is the fourth root of that, 2/5, so at least one car passes a 5-minute glance with probability 3/5.
She makes throw one, misses throw two, then scores with probability equal to her running make fraction. This Polya urn makes every tally from 1 to 99 equally likely after 100 throws, so exactly 50 makes has probability 1/99.
Each friend arrives at a uniform time in the hour and waits five minutes. Meeting means landing in a band of width 1/12 around the diagonal of the unit square, and the two leftover triangles have area 121/144, so they meet with probability 23/144.
Order two independent uniforms into a minimum Y and maximum Z. Pointwise YZ = X1 X2, so the mixed moment needs no joint density, and corr(Y,Z) comes out exactly 1/2.
For n independent uniforms the maximum has CDF z^n and mean n/(n+1), the minimum mirrors it with mean 1/(n+1), and the sorted draws cut [0,1] into n+1 gaps of equal expected length, which locates every order statistic at once.
M holds one dollar against N's two and wins each one-dollar game with probability 2/3, playing to ruin. The ruin recursion puts M's chance of taking everything at 4/7, the per-game edge just outweighing the bankroll deficit.
Thirteen cards each to four players. Placing the aces one at a time, the second avoids the first holder with probability 39/51, the third both holders with 26/50, the fourth 13/49, so every hand holds an ace with probability 2197/20825, about 0.105.
A jar of 10 red, 20 blue, and 30 green candies is drawn in uniform random order. Blue and green both outlast the reds exactly when the final red precedes the final blue and the final green, and comparing those three last positions gives 7/12.
Each minute an amoeba dies, idles, doubles, or triples with probability 1/4 each, descendants independent. Extinction probability is the smallest fixed point of the offspring generating function, and the root in [0,1) is sqrt(2) - 1, about 0.414.
Three dice rolled in order land strictly increasing in binom(6,3) = 20 of 216 outcomes, probability 5/54. The guess 1/6 conditions on three distinct values and forgets the ties, which is exactly where the count falls short.
The coin's bias is unknown. Toss it twice, read HT as heads and TH as tails, and discard ties. The two surviving outcomes each occur with probability p(1-p), so the extracted flip is exactly fair at any bias, paid for with a random number of tosses.
One coin in 1000 is double-headed and the rest are fair. Ten straight heads multiplies the odds by 2^10 = 1024, almost exactly cancelling the 999-to-1 prior, so the posterior probability of holding the fake is barely better than an even coin toss.
The last two digits of a cube depend only on x mod 100. Exactly one residue, 71, cubes to an ending of 11, so a uniform draw from 1 to 10^12 hits with probability 1/100.
One car and two goats sit behind three doors. After your pick, a host who knows the layout opens a goat door you did not choose and offers the remaining one. Whether to switch hinges on what his forced reveal says about your one-in-three first guess.
Two bullets sit in adjacent chambers and the first pull clicks empty. Of the four empty chambers only the one before the bullets kills the next pull, survival 3/4, while re-spinning resets survival to 2/3. Hold the cylinder still.
A random daughter answering the door is twice as likely in a two-girl family, which restores the probability of two girls to 1/2, while the bare statement that at least one child is a girl gives 1/3. The selection mechanism, not the fact, sets the answer.
Reveal shuffled cards until both water and earth appear, losing the moment fire shows. Wind is irrelevant, so the game reduces to whether fire comes last among the three live cards, and the winning probability is 1/3.
Mr. 10 fires first against Mr. 30 and Mr. 60. Any kill makes him the next target, while a deliberate miss lets the stronger pair thin each other and hands him the opening shot of the remaining duel. Missing on purpose maximises survival.
Twenty-seven unit pads double daily against a 6000-square-foot pond, so coverage requires 2^d >= 6000/27, about 222. With 2^7 = 128 short and 2^8 = 256 clear, the pond is blanketed on day 8.
One of twelve balls is heavy or light, unknown which, and each balance weighing returns one of three outcomes. Three weighings distinguish 27 outcomes against 24 possibilities, and the 4-4 schedule with reference balls decides every case.
Each rope burns end to end in exactly one hour at a nonuniform rate, so half the length is not half the time. A single flame consumes one minute of burn content per minute and two flames consume two, which is enough to measure exactly 45 minutes.
After 3:00 the minute hand gains 5.5 degrees per minute on a 90 degree deficit, so the hands first coincide 180/11 minutes past the hour, at 3:16:21 and 9/11 seconds.
At 3:15 the minute hand rests exactly on the 3 while the hour hand has crept past it by half a degree for each of the 15 minutes, leaving a gap of 7.5 degrees where the eye expects none.
Weather strips the outer layer from a 10 by 10 by 10 block of glued unit cubes. Counting the untouched 8 by 8 by 8 core instead of the shell's faces, edges, and corners gives 1000 - 512 = 488 fallen cubes in one subtraction.
Two tosses give four equally likely pairs. Assign HH, HT, and TH to the three children and re-toss on TT, so conditional on stopping each child wins with probability exactly 1/3 and the number of rounds is geometric with mean 4/3.
Five fair coins against four, winning on strictly more heads, succeed with probability exactly 1/2. Flipping every coin maps the head-count difference D to 1 - D, pairing each losing outcome with a winning one whatever the coin counts.
Repainting a random ball to a second random ball's colour merges colour classes one drawing at a time. From n singleton colours the expected time to a monochrome box is (n-1)^2, and the final two-colour merge alone accounts for half of it.
Five rational pirates vote on splits of 100 coins, failed proposers thrown overboard. Backward induction from the two-pirate endgame hands the most senior pirate (98, 0, 1, 0, 1), bought with the two cheapest votes aboard.
n customers hold fives, n hold tens, and the seller starts with no change. Serving everyone requires each prefix of the line to hold at least as many fives as tens, a ballot condition counted by the Catalan numbers, giving probability 1/(n+1).
The dial sums to 78, so three equal arcs need 26 each. The arcs forced around 12 and around 11 leave {3, 4, 9, 10}, two clumps on opposite sides rather than one arc, so no split into three unbroken pieces exists. Arithmetic permits what geometry refuses.
One of ten bags of 100 coins is counterfeit, each of its coins a gram heavy or a gram light. Weighing i coins from bag i makes the exact reading deviate from 550 grams by the bag's index, and the sign of the deviation tells heavy from light.
Ninety-eight distinct integers from 1 to 100 stream past once, leaving two values unseen. Running totals of the sum and the sum of squares recover both, and an xor plus a bit split does the same without large intermediate numbers.
A bowl holds 100 noodles, hence 200 loose ends. Tying uniformly random pairs of ends until none remain produces on average 1 + 1/3 + ... + 1/199 loops, about 3.28, because a tie made with 2k ends left closes a loop with probability 1/(2k-1).
Five hundred point ants walk at unit speed from uniform positions on a unit string, reversing at every head-on collision. Reversals merely relabel the ants, so the last fall time is the maximum of 500 one-way walks, with expectation 500/501 of a minute.
Six chambers, one bullet, one spin, then alternating trigger pulls with no re-spin. The bullet sits uniformly in one of six pull slots, three odd and three even, so first and second player lose equally often and only re-spinning would break the tie.
A and B toss a fair coin alternately, A first, and whoever throws the tail completing the first head-then-tail pair wins. Conditioning on the last-toss state gives A exactly 4/9. Tossing first mostly means laying the head that the opponent's tail finishes.
A free ticket goes to the first person in line whose birthday matches someone ahead of them. Position k wins with probability (k-1)/365 times the chance of no earlier match among k-1 predecessors, a product maximised at k = 20.
Jason's second dart lands farther out than his first. Conditional on that, the third also lands farther than the first with probability 2/3, since the six rankings of three exchangeable distances are uniform and the conditioning marks the first throw as good.
Couples bear children until the first girl, then stop, each birth fair and independent. The rule only decides family size, so the population fraction of girls stays 1/2 by the law of large numbers, boys concentrating in long families without ever outnumbering.
A mother of two is invited to a dinner open only to mothers with at least one son. The invitation names no particular child, so BB, BG, and GB stay equally likely and both boys has probability 1/3, not 1/2.
Can seven prisoners, each seeing six of seven arbitrary rainbow hats but never his own, coordinate one simultaneous guess apiece so that someone is always right?
Matching reds pay A three dollars, matching blues one, and any mismatch pays B two, all from an outside bank. The mixed-strategy equilibrium values B at 1.00 dollars against A's 0.75, the steady prize beating the rare one.
A 40 percent three wins outright. A 70 percent two only forces overtime worth a coin flip, discounting it to 35 percent. Take the three, because playing for the tie halves the value of the make.
Four equal sections pay 1 dollar and the fifth pays 5, so a spin returns 9/5 = 1.80 dollars on average against a 1.50 ticket. The 30-cent edge makes a single spin worth taking, and repetition only compounds it.
Four fair-coin matches parlay to a 1/16 win probability, so 10-to-1 loses 5/16 per dollar while 25-to-1 gains 5/8. The break-even odds are exactly 15-to-1.
The switching argument prices the other envelope at 5A/4 by letting one symbol A denote m in one branch and 2m in the other. Conditioning on the actual pair values both envelopes at 3m/2, so switching gains nothing.
Roll until a non-one appears and collect that face in dollars. Conditioning on stopping makes the winning face uniform on 2 through 6, so rerolls cost time while the expected payoff is simply their mean, 4 dollars.
A 52-card deck is dealt in 26 pairs, black-black to the dealer, red-red to you, mixed discarded, and a strictly bigger pile wins $100. Each mixed pair removes one red and one black, so the piles tie on every deal and the fair entry price is zero.
One roll of a fair die pays its face value in dollars, expected value 3.5. The fair ticket price is exactly 3.50 dollars, and anything above it is the seller's compensation for risk or margin.
A call plus K e^(-rT) in bonds pays the same at expiry as a put plus the stock, so absence of arbitrage forces C - P = S - K e^(-rT) at every earlier time, with no assumption on the stock's dynamics.
Before expiry a call on a non-dividend stock satisfies C >= S - K e^(-rT) > S - K, so it is always worth more alive than exercised. Early exercise surrenders interest on the strike and the downside floor, making American and European prices coincide.
Geometric Brownian stock, constant rate and volatility, no dividends, frictionless continuous trading, no arbitrage. Together these make the delta hedge exact, so the price solves the Black-Scholes PDE and the drift drops out of the formula.
Up to three rolls, keep the face shown or forfeit it and roll on. Backward induction values the last roll at 3.5, so stop at 4 or better on roll two and 5 or better on roll one, pricing the game at 14/3, about 4.67 dollars.
Log returns add across years and independence adds their variances, so the four-year variance is four times the annual and volatility scales as sqrt(T), 20 percent at four years. Simple returns compound multiplicatively and obey no such rule.
Reds pay a dollar, blacks cost one, and you may stop the deal at any point. The optimal rule compares banked profit with the continuation value, and the fresh 26-26 deck is worth about 2.62 dollars, entirely the option value of quitting while ahead.
Faces 1 to 5 add to your bank, a 6 erases it and ends the game, and you may stop after any roll. Stopping is optimal once the bank reaches 15, where a roll risks more than the 2.5 it expects to add, and the recursion prices the game near 6.15 dollars.
Bond A defaults with probability 0.5, bond B with 0.3, dependence unspecified. Frechet bounds put at least one default anywhere in [0.5, 0.8] and the default correlation in [-0.65, 0.65], the price of leaving the joint law free.
Hedging one share of A with h short shares of B minimises variance at h* = rho sigma_A / sigma_B. The residual is sigma_A^2 (1 - rho^2), so the hedge removes exactly the squared-correlation share of the risk and an uncorrelated B removes none.
Each roll pays its face value and a 4, 5, or 6 buys another roll. The renewal equation E = 3.5 + E/2 gives an expected payoff of 7 dollars, one average face doubled by an average of two rolls.
Pairing 1 with n, 2 with n-1, and so on yields n/2 pairs each summing to n+1, hence 1 + ... + n = n(n+1)/2 and 5050 for n = 100, one multiplication in place of ninety-nine additions.
Assume a lowest-terms ratio of integers squares to 2. Parity forces both numerator and denominator even, contradicting the reduction. The same descent rules out sqrt(p) for every prime p.