Probability interview

Hi, I'm Alex. This is the probability round: about thirty minutes, five problems, no paper needed. Reason out loud; rough numbers are fine, and I care about how you get there as much as the answer. Before we start, what are you working on these days?

Hi. I'm in the last year of a maths degree, with a lot of statistics. My dissertation is on stopping rules for sequential trials, so, um, when you're allowed to stop collecting data and still trust the result. And for fun I'm in a trading-game society at university, the Ravensmoor Trading Club, where we make markets on silly things for fake money, like the number of pigeons in the square at noon.

Okay. What have the trading games taught you so far?

Mostly that my first guess is usually too confident. When you quote a tight market on something you know nothing about, the people who trade with you are the ones who know more. So I've learned to quote wide first and narrow as I learn. And to do quick sums without freezing, which I hope helps today.

Okay. First problem. You flip a fair coin repeatedly. What is the expected number of flips until you first see heads twice in a row?

Um, two heads in a row has probability a quarter, so... four flips?

Check that against a simpler case. How long until the first single head?

Two. And one over a half is two, so that matches. Hmm, but for two in a row the tries overlap, a tail after one head throws away the progress, so it's not independent tries of two flips. The one-over-p formula only works for independent attempts. Let me use states. E0 is the expected flips from scratch, E1 after one head. From scratch I flip once: half the time I get a head and go to E1, half the time a tail and I'm back at E0. So E0 is 1 plus half E1 plus half E0. From E1, I flip once: a head finishes, a tail sends me back to the start. So E1 is 1 plus half times zero plus half E0. Substituting, E0 is 1 plus half of 1 plus a quarter E0 plus half E0, so 1.5 plus three quarters E0. A quarter of E0 is 1.5, and E0 is 6.

Sanity check?

It should be more than four, because of the restarts, and six is more than four. Another way: you need a head first, that's two flips on average, then the next flip is a head half the time, and a miss costs you the whole thing again. If I simulate it roughly in my head, it's around six. And for E1, it's 1 plus 3, so 4, which is also bigger than 2. It hangs together.

What about three heads in a row?

Same states with one more. The pattern from one and two heads is 2 and 6, each one is double the previous plus two, so three heads is 14.

Why double plus two?

Um, to get n in a row, first get n minus one in a row, that's E of n minus one. Then flip once more: half the time it's heads and I'm done, half the time it's tails and I start over from zero, with E n still to go. So E n is E n minus one plus 1 plus half E n. Half E n equals E n minus one plus 1, so E n is two E n minus one plus two. Okay, so it's not just a pattern, it's the recursion. Good, I was a bit uneasy about that.

And the general formula for n in a row?

If I add two to both sides, E n plus 2 is two times E n minus one plus 2, so E n plus 2 doubles each time, starting from E0 plus 2, which is 2. So E n plus 2 is two to the n plus one, and E n is two to the n plus one, minus two. For n equal to 2 that's 8 minus 2, 6. For three, 16 minus 2, 14.

Now the expected number of flips until you first see heads followed by tails.

Heads then tails. Also two specific flips, so... also 6? Hmm, wait, wait. Let me do the states again. From scratch, flip until I get a head, that's 2 on average. Once I have a head, a tail finishes it, and another head doesn't hurt me, I'm still sitting on a head. So I never go back to the start. From there it's waiting for a tail, another 2. So 4, not 6.

Why is it different from heads-heads?

Because with heads-heads, a failure throws away the progress: a tail after a head puts me at zero. With heads-tails, a failure, another head, keeps me where I was. The pattern overlaps with itself for heads-heads and not for heads-tails, I think that's the general idea, the self-overlap is what makes it slower.

Variance of the number of flips for heads-heads?

Um. I'd set up the same states for the second moment, E of N squared from each state, and solve the linear equations. I don't know the number offhand and I don't think I can do it cleanly in my head right now. I'd guess it's large, the distribution has a long tail, maybe a standard deviation around the same size as the mean.

Next. You roll a fair die and are paid the number shown in dollars. You may roll once more and take the second result instead. What is the game worth, and what is your strategy?

Work backwards from the last decision. If I reroll, I get a fresh roll, worth 3.5 on average. So I keep anything above 3.5: keep 4, 5 or 6, and reroll 1, 2 or 3. Half the time I keep, and the average of 4, 5 and 6 is 5, so that's 2.5. Half the time I reroll and get 3.5 on average, that's 1.75. So 2.5 plus 1.75, 4.25 dollars.

What if you may reroll up to two times?

Then I use the same rule again: keep 4, 5 or 6 on the first roll, otherwise play the one-reroll game. That's 2.5 plus half of 4.25, so 4.625.

Is a 4 worth keeping when rolling on is worth 4.25?

Oh. No, it isn't. I reused the old threshold; the threshold should be the value of continuing, which is now 4.25, not 3.5. So I only keep a 5 or a 6. That's 5 plus 6 over 6, plus four sixths of 4.25. 11 sixths plus... four times 4.25 is 17, so 17 sixths. 28 sixths, about 4.67.

Sanity check?

It has to be more than 4.25, since an extra option can't hurt, and less than 6. And the jump is smaller than from 3.5 to 4.25, which makes sense, each extra roll is worth less. 4.67 fits.

What's the general principle behind the threshold?

Backward induction. At every decision, compare what you have now with the expected value of continuing optimally from there, and you can only compute that from the end backwards. Each extra reroll raises the value of continuing, so the threshold goes up. It's the same thing I do in my dissertation, actually, with stopping a trial early, just with dice instead of patients.

What if each reroll costs a dollar? One reroll.

Then rolling on is worth 3.5 minus 1, so 2.5. So I keep anything at least 3, and reroll a 1 or a 2. Value: keeping 3, 4, 5, 6 gives 18 over 6, that's 3. Plus two sixths times 2.5, which is, um, 5 sixths, about 0.83. So about 3.83.

Check?

Without rerolling the game is worth 3.5, so 3.83 is above that but below the free version, 4.25. And you only reroll the really bad rolls now, which makes sense when it costs something. Fits.

How much would you pay to play the original game, once?

If I'm risk neutral, up to 4.25. In practice a bit less, to have an edge, and it's only once, so the variance is large compared to the stake. Maybe 4 dollars. If it were a thousand times I'd pay close to 4.25.

Now unlimited rerolls, each costing a dollar. What's it worth?

Okay. Now the game looks the same after every roll, so the value V is the same every time. If I reroll I get V minus 1. So I keep a roll if it's at least V minus 1. Guess a threshold and check it. Keep 5 or 6: V is 11 over 6 plus four sixths of V minus 1. So V minus two thirds V is 11 sixths minus 4 sixths, a third of V is 7 sixths, V is 3.5. Hmm. That's no better than not playing on.

What are you thinking?

That keeping only 5 and 6 is too picky, I'm paying too much in rerolls. Try keep 4 and up: V is 15 over 6 plus a half of V minus 1. Half of V is 2.5 minus 0.5, 2, so V is 4. Then continuing is worth V minus 1, which is 3, so a 4 is worth keeping, and a 3 is exactly indifferent. Keep 3 and up gives the same: 18 sixths plus a third of V minus 1, two thirds V is 3 minus a third, V is 4. So it's worth 4, keep anything 4 or above, and it doesn't matter what you do with a 3.

Next. How many people do you need in a room so that the chance that two share a birthday exceeds 50%?

My gut says something like 183, half of 365, but I know that's the classic trap, because it's pairs that matter, not people. With n people there are n squared over two pairs. Let me do it properly. I'll assume 365 equally likely days, no leap years, no twins.

Go on.

The probability that all birthdays are different with n people is 364 over 365, times 363 over 365, and so on, down to 365 minus n plus 1. Each factor is 1 minus k over 365, which is about e to the minus k over 365 for small k. So the product is e to the minus the sum of k, and the sum is n times n minus 1 over 2, roughly n squared over 2. So it's about e to the minus n squared over 730. Set that to a half: n squared over 730 is ln 2, 0.69. So n squared is about... 730 times 0.69, um, 700 times 0.69 is 483, plus 21, 504. Square root of 504, about 22.4. So 23 people.

Is the approximation good enough to pick 23 over 22?

Hmm. It's borderline. If I use n times n minus one instead of n squared, then 23 times 22 is 506, which is just over 504, and 22 times 21 is 462, under. So 23 is the first one past a half. The exponential approximation slightly overestimates each factor, but I don't think it moves it by a whole person. I'd want to check it exactly, but I'm fairly confident.

With 23 people, what's the expected number of pairs sharing a birthday?

23 choose 2 pairs, that's 23 times 22 over 2, 253. Each pair matches with probability 1 over 365. 253 over 365 is about 0.69. Oh, that's ln 2 again, which makes sense, it's the same exponent as before. So on average less than one matching pair, even though the chance of at least one is just over half.

Does ignoring leap years matter?

Barely. February 29th has about a quarter of a day's weight, so it's like 365.25 days with one tiny day. That makes matches very slightly less likely, but it won't move 23. I'd ignore it.

What if we want 99%?

Then e to the minus n squared over 730 is 0.01. ln of 100 is about 4.6. So n squared is 730 times 4.6, um, 730 times 4 is 2,920, plus 730 times 0.6, 438, so 3,358. Square root... 58 squared is 3,364. So about 57 or 58. I can't tell which one without doing it exactly.

How does the answer change if birthdays are not uniform?

It goes down. Uneven days make collisions more likely, because people pile up on the popular days. Uniform is the worst case for matching. I can't prove it right now, but I think it's a convexity argument, the chance of a match for a pair is the sum of p squared over days, and that's smallest when all the p are equal.

Next. A family has two children and at least one is a boy. What is the probability both are boys? Now, what if you are told the older child is a boy?

Assuming boys and girls are equally likely and independent. The cases are boy-boy, boy-girl, girl-boy, girl-girl, ordered by age, each a quarter. At least one boy removes girl-girl, so three cases are left, and one of them is boy-boy: one in three. If the older one is a boy, only boy-boy and boy-girl are left, so one half.

Why does the second piece of information change the answer?

Because it points at one specific child. At least one boy keeps both mixed cases, the older one is a boy keeps only one of them. Once you know which child is the boy, the other one is just a fair coin.

What are you assuming about how you learned there's a boy?

Hmm, good point. I'm assuming the information is 'we checked the family and it has at least one boy'. If instead you met one of the children at random and it happened to be a boy, then it's like the older-child case, you've picked out a specific child, and the answer is a half. So the answer depends on how the information was produced, not just what it says.

What if you are told at least one is a boy born on a Tuesday?

Hmm. The day shouldn't matter, it's independent of everything, so I'd say it's still one third.

Try counting it.

Okay. Each child is one of 14 types, sex and day, all equally likely. Pairs with at least one Tuesday boy: everything minus the pairs with no Tuesday boy, 14 squared minus 13 squared, 196 minus 169, 27. Both boys with at least one Tuesday boy: each is one of 7 boy types, so 7 squared minus 6 squared, 49 minus 36, 13. So 13 over 27. Huh, so it does matter. The Tuesday detail almost picks out one child, so it moves the answer toward one half.

And if it were a boy born on the first of January?

Same logic with 365 days instead of 7. That's even more specific, so it's very close to a half. By the same formula: two times 365 minus 1 over four times 365 minus 1, so 729 over 1,459. Just under a half.

Does that formula give 13 over 27 for Tuesday?

Two times 7 minus 1 is 13, four times 7 minus 1 is 27. Yes. And with one day it's 1 over 3, which is the original problem. Nice, so it goes from a third to a half as the detail gets more specific.

How would you explain the Tuesday result to someone who thinks it's a trick?

I'd say: the extra detail changes how many families fit the description. Families with two boys have two chances to contain a Tuesday boy, families with one boy have only one. So two-boy families are overrepresented among the ones that fit, almost twice as much, and that pushes it toward a half. It's not about Tuesday, it's about how the information was selected.

Last one. Estimate how many piano tuners work in a city of one million people. Talk me through your assumptions.

Okay. Demand side first, then supply. A million people, about two and a half per household, so 400,000 households. What fraction has a piano... I'd say one in twenty, so 20,000 pianos in homes. Plus schools, churches, concert halls, music schools, maybe another 2,000. So round it to 22,000 pianos.

How often are they tuned?

Officially once or twice a year, but a lot of home pianos are never tuned. Say on average once every two years at home and once a year for the institutional ones. So 10,000 plus 2,000, call it 12,000 tunings a year. Um, institutional ones maybe more, concert pianos get tuned before every concert, but there are very few of them, so I'll ignore that.

Oh, and grands versus uprights, grands are usually tuned more often, and the ones in concert halls are tuned—

Keep it to the count.

Supply side?

A tuning takes about an hour and a half, plus travel. So maybe eight a day... no, that's too many with travel, that's twelve hours of tuning alone. Four a day is more realistic. 250 working days, so a thousand tunings a year per full-time tuner. 12,000 over 1,000 is 12 tuners.

Sanity check?

Hmm. Twelve feels low for a city of a million. Many tuners are part-time, and they also repair and restore pianos and teach, so the headcount would be higher than the full-time equivalent, maybe double. And my one in twenty might be low for an older city. So I'd say somewhere between 15 and 40, with 25 as my point estimate.

Which assumption is the most uncertain and how would you narrow it?

The share of households with a piano. It could be one in ten or one in fifty depending on the city, and everything scales linearly with it. I'd narrow it with piano sales or ownership survey data, or just count the tuners listed in a local directory and work backwards to check the whole chain. If the directory says 60, then one of my assumptions is off by a factor of two, probably that one.

What changes for a city of ten million?

Roughly linear, so about ten times, 150 to 400. Maybe a bit less per person, big cities have more small flats with no room for a piano, but tuners also travel less between jobs in a dense city, so each one does more tunings. I'd still say roughly ten times.

How confident are you in the 25?

Not very. I'd say a factor of two either way is plausible, so maybe an 80 percent interval of 12 to 50. Every step in the chain is a guess, but at least the errors partly cancel: if I overestimated the pianos, I probably also overestimated how often they're tuned... no, that makes it worse, they go in the same direction. So the interval should be wider, not narrower.

If you had to make a market on the number, what would you quote?

Given how uncertain the piano share is, wide. Something like 15 bid, 45 offered. And I'd lean higher rather than lower, because the part-time effect only pushes it up.

Someone sells to you at 15 straight away. What now?

Then they probably think it's below 15, maybe they've looked it up. I'd lower my market, maybe 10 at 25, and be careful about buying more from them. Unless I think they're just testing me, but the first rule in the club is that the person who trades fast usually knows something.

Okay. That's the five. We have a few minutes left. Any questions for me?

Yes. How much of the day-to-day uses this kind of quick probability, versus longer research?

It depends a lot on the desk and the role. Quick reasoning like this comes up daily in some seats and rarely in others. The hiring team can tell you about the specific role.

Okay. And, um, is the next round more coding or more of this?

That depends on the process for the role. The recruiter will have the schedule.

And, um, how do you usually find out whether someone just memorised these puzzles?

Mostly with follow-ups and variations, like the ones today. A memorised answer doesn't extend well.

Fair. Okay, thank you, that's all.

Thanks, that's the round. The report will be ready in a few minutes.