Example Jane Street Interview Questions

This is a pretty straightforward Markov chain problem. There are 4 states. The transition graph is given in Figure 1.

The problem starts at state 1. As has been explained in the lessons of this course, we use the following equation:
\begin{equation}
s_1 = \sum_{i=0}^{3}p_{1,i}s_i
\end{equation} \begin{equation}
s_2 = \sum_{i=0}^{3}p_{2,i}s_i
\end{equation} Furthermore, $s_0=0$ and $s_3=1$. Then we have
\begin{equation}
s_1 = \frac{1}{3}*0 + \frac{2}{3} * s_2
\end{equation} \begin{equation}
s_2 = \frac{1}{3}* s_1 + \frac{2}{3} * 1
\end{equation} Solving these equations gives us $s_1=4/7$ and $s_2=6/7$. So, starting with 1 dollar, player A has a 4/7 chance of winning.

Proof
If we substitute Equation 4 in Equation 3, we have

\begin{equation}
s_1 = \frac{1}{3}*0 + \frac{2}{3} * (\frac{1}{3}* s_1 + \frac{2}{3} * 1)
\end{equation} \begin{equation}
s_1 = \frac{2}{9} * s_1 + \frac{4}{9}
\end{equation}  \begin{equation}
\frac{7}{9} * s_1 =  \frac{4}{9}
\end{equation}  \begin{equation}
s_1 =  \frac{4}{9} / \frac{7}{9} = \frac{4}{7}
\end{equation}

This is called the coupon collector problem. For a fair n-sided die, the expected number of attempts needed to get all n values is \begin{equation}
n \Sigma_{k=1}^n \frac{1}{k}
\end{equation} which, for large n is approximately n log n.

The time until the first result appears is 1. After that, the random time until a second (different) result appears is geometrically distributed with parameter of success 5/6, hence with mean 6/5 (recall that the mean of a geometrically distributed random variable is the inverse of its parameter). After that, the random time until a third (different) result appears is geometrically distributed with parameter of success 4/6, hence with mean 6/4. And so on, until the random time of appearance of the last and sixth result, which is geometrically distributed with parameter of success 1/6, hence with mean 6/1. This shows that the mean total time to get all six results is \begin{equation}
6 \Sigma_{k=1}^6 \frac{1}{k} = \frac{147}{10} = 14.7
\end{equation}

For the outcome to be even is the same as the outcome not being odd. For the outcome to be odd, all three dice need to be odd, respectively:

• 1*1*1 = 1 (odd)
• 3*3*3 = 27 (odd)
• 5*5*5 = 125 (odd)

and also all combinations of the odd numbers result in odd outcomes, like:

• 1*1*3 = 3 (odd)
• 3*3*5 = 45 (odd)
• etc.

Basically, multiplying odd numbers with each other results in an odd outcome. If ANY even number comes in play, then we have "a number" multiplying "an even number", which will always result in an even number. So, "odd * even * odd" will also result in even.

So, in any other scenario than multiplying three odd numbers, the product will be even. Therefore, the probability that the product is even is, given that half of the sides of the dice are odd ({1,3,5} vs {2,4,6}) equal to \begin{equation} P(even \; product) = 1 - P(only \; odd \; product) \end{equation} \begin{equation} P(even \; product) = 1 - (\frac{1}{2})^3 = \frac{7}{8} \end{equation}

Before solving, let's name the one idea behind this game: backward induction for an optimal stopping decision. When you face a "keep it or try again" choice, you compare what you already have against the expected value of the alternative, and you keep what you have only when it is at least as good.

What is a fresh roll worth?
If you discard the first roll, you are paid whatever the second roll shows, with no further choices. The second roll is a fair eight-sided die, so its expected value is the average of the faces: \begin{equation} E[\text{reroll}] = \frac{1 + 2 + 3 + 4 + 5 + 6 + 7 + 8}{8} = \frac{36}{8} = 4.5 \end{equation} So choosing to re-roll is worth $4.5$ on average, no matter what the first roll was.

The decision rule
After seeing the first roll $v$, you choose the better of two options: keep $v$, worth $v$, or re-roll, worth $4.5$. You therefore keep the first roll exactly when \begin{equation} v \geq 4.5 \end{equation} that is, when $v \in \{5, 6, 7, 8\}$, and you re-roll when $v \in \{1, 2, 3, 4\}$.

Computing the game's value
Each first-roll value $v$ occurs with probability $\frac{1}{8}$. For the four low values you re-roll and collect $4.5$; for the four high values you keep $v$. So the fair value is \begin{equation} E[\text{game}] = \frac{1}{8}\Big(\underbrace{4.5 + 4.5 + 4.5 + 4.5}_{v = 1,2,3,4 \text{, re-roll}} + \underbrace{5 + 6 + 7 + 8}_{v = 5,6,7,8 \text{, keep}}\Big) \end{equation} \begin{equation} E[\text{game}] = \frac{1}{8}\big(18 + 26\big) = \frac{44}{8} = 5.5 \end{equation} Notice the value 5.5 sits comfortably above the 4.5 you would get from a single roll with no choice: the option to re-roll the bad half of the die is worth exactly one extra point.

So, the fair value of this game is 5.5