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}