Dip Above 100
Jane Street
You roll a 4 sided die and sequentially add up the score seen. What is the expected value of the first number you see above 100?
Answer
To find expected value, we need all the possible outcomes and their probabilities. Which numbers can we dip above the sum of 100 with? With 101, 102, 103 and 104. Why not 105? Because the biggest roll we can get is 4, so to reach 105 the sum must have been at least 101 on the previous roll - and therefore 105 cannot be the first number we see above 100.
Now let's handle the probabilities. We can reach 101 as the first number above 100 by rolling a 1 if we were previously at 100, with 2 if we were at 99, 3 if we were at 98 or 4 if we were at 97 - 4 possible scenarios. Notice the condition: we must previously be at a sum up to 100, and have this last roll dip above 100. Similarly, we can dip to 102 with a 2 if previously at 100, a 3 if previously at 99 or 4 if previously at 98 - 3 possible scenarios. We get to 103 only with a 3 if previously at 100, or 4 if previously at 99. And lastly we get 104 as the first number above 100 only if we had 100 before and we roll a 4.
It is safe to assume that probabilities of being at 97, 98, 99 and 100 are all equally likely to be the last sum before dipping above 100. They are indeed close enough, and it's prohibitive to compute exact probabilities on the interviews, so simply assume each of them has the same probability $p$.
Further, we know probability of rolling any value 1-4 is $\frac{1}{4}$. Therefore, the probability of dipping above any of the scenarios we mentioned (e.g. having 99 then rolling a 3) has the probability $p \cdot \frac{1}{4}$. Now we know that we reach 100 with one of the outlined scenarios, so all their probabilities sum up to 1. We had 4 cases where 101 is the first number above 100, 3 ways where it's 102, 2 ways for 103 and 1 way for 104 - 10 possible scenarios in total. Therefore, $10\cdot p \cdot \frac{1}{4}=1$. In turn, $p=\frac{2}{5}$, and any scenario has probability $\frac{1}{4}\cdot \frac{2}{5}=\frac{1}{10}$.
Now, since 101 can happen in 4 ways, all of which have probability $\frac{1}{10}$, then 101 is the first number to dip above 100 with probability $\frac{4}{10}$. It's 102 with probability $\frac{3}{10}$, 103 with probability $\frac{2}{10}$ and 104 with probability $\frac{1}{10}$. The expected first number can then be obtained as $$\frac{4}{10}101 + \frac{3}{10}102 + \frac{2}{10}103 + \frac{1}{10}104=102$$