Dare to solve this quant interview brain teaser?
Quantitative finance interviews — aka “quant interviews” — are known for their rigor and intensity. They often feature challenging brain teasers rooted in probability and statistics. These problems test not just your mathematical prowess but also your ability to think critically and solve complex issues under pressure. Among the variety of topics covered, probability and statistics stand out as go-to questions for several reasons.
Firstly, probability and statistics are foundational to the financial models and algorithms used in trading, risk management, and investment strategies. Understanding these principles is essential for quant roles, as they underpin the behavior of financial markets and instruments. Interviewers use these questions to gauge your theoretical knowledge and practical problem-solving skills, ensuring you can apply mathematical concepts to real-world scenarios.
Secondly, questions in probability and statistics can reveal a candidate’s depth of understanding and their ability to approach problems methodically. These questions often require a blend of intuition and analytical thinking, qualities that are crucial for success in quantitative finance. For instance, problems may involve stochastic processes, Bayesian inference, or combinatorial analysis, all of which are integral to developing robust financial models.
To illustrate the application of these principles, let’s dive into an example. The following problem is a slight generalization of an exercise proposed in Chapter 2 of Blitzstein and Hwang’s Introduction to Probability:
There are N equally spaced points around a circle. At N-1 of the points, there are sheep, and at 1 point, there is a wolf. At each time step, the wolf randomly moves either clockwise or counterclockwise by 1 point. If there is a sheep at that point, he eats it. The sheep don’t move. What is the probability that the sheep who is initially opposite the wolf is the last one remaining?
This question is very similar to a question I received while interviewing for a famous quant firm in the US (of course, because of non-disclosure agreements, I cannot reveal the original question). In fact, the periodicity of the problem with the sheep placed around a circle introduces an additional layer of complexity. I think it’s therefore an excellent training question for everyone who is preparing to apply for quant jobs. By exploring this problem, we will see how to leverage symmetry, conditional probabilities, and recursive calculations to arrive at a solution. Let’s get started!
How to approach the question
You should immediately recognize that this problem is probabilistic in nature, since the wolf moves is said to move randomly. More specifically, it’s an instance of an unbiased random walk on a circle. If you are already familiar with circular random walks, you should know that in the long-time limit, any point has the same probability 1/N of being visited. However, since one spot is always occupied by the wolf and there N-1 sheep that can be eaten, we’re restricting the value space to N-1 points on the circle. Intuitively, then, the probability should be 1/(N-1).
It turns out that this is indeed the correct answer, but the interviewer might be interested in a more detailed explanation and a rigorous mathematical breakdown of how to get there. So, let’s delve a little bit deeper into the problem. The probabilistic/stochastic nature of the problem makes it amenable to many different approaches.
One could involve an analysis through Markov chains. We could define states based on the position of the wolf relative to the sheep, construct a transition matrix where each entry represents the probability of transitioning between different states, and identify and solving for the absorbing states corresponding to the scenarios where only one sheep remains. In my opinion, however, Markov chains are higher-grade weaponry compared to the complexity of the problem. Furthermore, they usually involve calculating matrix eigenvalues which cannot be done with pen and paper.
Another approach could be to simply run a Monte Carlo simulation of the problem, and in fact we’ll do just that below to check our solution. However, we will show below that there exists a closed form for this problem. Simulations are usually best for (portions of) problems that are otherwise not analytically tractable. Moreover, in a quant interview you don’t always have the freedom to quickly code and solve the problem numerically. Nevertheless, if you don’t know where to start, simulating the problem and looking for patterns that might suggest a potential generic solution is always a good idea!
Since the first two approaches seem a bit too cumbersome, let’s tackle the problem with good ol’ fashioned Bayesian probability theory! We will show that:
- We can exploit the inherent symmetry of the problem.
- We can break down the problem into simpler chunks that amount to solve a simpler Gambler’s ruin problem, which I wrote about last week.
The solution
To make our notation clearer and facilitate a later visualization in polar coordinates, we number the points anticlockwise from 0 (starting at 3 o’clock) to N-1. Therefore, the wolf initially sits at position 0, and we are interested in the probability that he eats the sheep sitting opposite to him, at 9 o’clock last.
First, let us note that since the wolf is moving with equal probability to the left and to the right on a circle, each sheep has the same probability of being eaten last. This might seem counterintuitive at first: after all, sheep #1 is so close to the wolf that it certainly must be eaten early on in the sequence, right? That would be true if the setup had open boundary conditions (i.e. a chain with a “beginning” and an “end”), but because the sheep are arranged on a circle, the fast path directly to #1 is compensated by many long paths that wind all around the circle before reaching #1 from the opposite direction. We will verify this finding in the numerics later on.
Since we established that all sheep have the same probability of being eaten last, let’s consider a generic #i. For sheep i to be the last one remaining, the wolf must eat both the one at i-1 and at i+1 first. Let us define the following events:
- E_i: the event that the wolf eats sheep #i last.
- E_{i-1>i+1}: the event that the wolf eats sheep #(i-1) before sheep #(i+1).
- E_{i-1>i+1}: the event that the wolf eats sheep #(i+1) before sheep #(i-1).
Note that the last two events are complements to each other and thus they partition the sample space into two disjoint sectors.
Now, if you follow this blog you should know that a very powerful tool in probability that comes up over and over again is conditioning. Conditioning is used to rewrite hard-to-calculate prior probabilities in terms of conditional or posterior probabilities that we know how to calculate more easily. This is done by using the law of total probability (LOTP), as explained in this problem, in this one, and this one. For the problem at hand, we will condition the event E_i — whose probability we are after — on the two disjoint events E_{i-1>i+1} and E_{i+1>i-1}. The idea is that sheep i can be reached only in two ways, either from i-1 or from i+1. If we know that i-1 is eaten before i+1 (or vice versa) we have only one possible path that ends at i, which we can calculate more easily. This is an instance of a technique called first step analysis that is employed to break down iterative problems in smaller bits that are easier to handle.
Using the LOTP, we can write:
and we can now separately calculate the two factors in each summand.
P(E_{i-1>i+1}):
Since i-1 must be reached before i+1, we can neglect point i altogether. This naturally introduces two points where we can “cut” the circle and flatten it out to a line that goes from i+1 (left end) to i-1 (right end) in steps of one. This chunk of the problem thus maps exactly onto an unbiased (p=1/2) Gambler’s ruin problem where player A starts with N-i-1 dollars, player B starts with i-1, and the total wealth among the two is N-2 dollars. If this notation is too abstract for you, take a look at the sketch below for N=100.
Since i-1 corresponds to the right end and it has to be reached first, we are essentially looking for the winning probability in this Gambler’s ruin problem. If you already know about Gambler’s ruin, you should recall that the probability of winning when starting with $j and a total shared wealth w is simply j/w. Plugging in the numbers for this specific case, we thus conclude:
P(E_{i+1>i-1}):
The probability of reaching i+1 before i-1 is calculated by using the same trick and exploiting the symmetry of the problem, whereby we simply swap the left and right end. We are thus playing a Gambler’s ruin game starting with i-1 dollars and want to reach N-2. The probability for that is accordingly
P(E_i | E_{i-1>i+1}):
To calculate this conditional probability, we will again map it to a simpler Gambler’s ruin setup. Since i-1 has been eaten before i+1 (we are writing this as a condition that has happened), in the probability above we are effectively asking the probability of going from i-1 to i through i+1. We can then cut the circle at i and i+1=N-i+1, and unfold it into a straight line with points at i, i-1, i-2, …, 0, N-1, N-2, …, N-i+1 (see again sketch below for a visual).
Since now we are starting at i-1, this problem is an unbiased Gambler’s ruin problem where player A starts at $1 with a total wealth of N-1 dollars. The winning probability is then
Again by symmetry (flipping left/right end), we immediately obtain the same probability for the opposite case where we start from i+1 and move to i through i-1:
Putting things together:
Now that we have calculated all the probabilities, we can put them together to arrive at the solution:
Our initial intuition was right! The probability is indeed the inverse of the number of sheep.
Let’s run some simulations!
To conclude this analysis, let’s run some simulations for the problem to confirm our analytical solution. We want to confirm two things:
- All the sheep have the same probability of being eaten last.
- This probability is the inverse of the number of sheep.
To show this, I wrote a jupyter notebook that simulates the circular random walk of the wolf for a high number of iterations, and checks which sheep is being eaten last every time. By tracking the wolf movement and the sequence of sheep he eats, we can nicely visualize the problem and collate the results into an empirical probability distribution. You can find the code in my Gitlab repository below. Feel free to download it and play around with it!
I’ve run tests with N=20, 50, and 100. The larger the system size, the more iterations you need in the Monte Carlo simulation to achieve the same precision in the empirical distribution. In most of the figures below, I thus stick with the N=50 simulations.
Below is an example of the path that the wolf takes during one of the 10'000 realizations I simulated (this takes about a minute on a modern laptop). The thicker the line, the more often the wolf visits that area. You can see that some points are visited many times because of the wolf’s random back and forth. The last sheep eaten in this particular run was #28.
We can also check how often sheep #25 is eaten (the one sitting opposite to the wolf) to verify our 1/(N-1) result. In my simulations with N=50, I obtained a value of 0.0225, which is pretty close to the exact value 1/49~0.020408.
Finally, we can justify our comments about symmetry by verifying that the distribution of which sheep gets eaten last approaches a uniform distribution. We can do that by collecting how many times each sheep gets eaten last in the simulations and plotting the corresponding results as (normalized) histograms. This is shown below for N=50, and you can see that — while there are fluctuations — each sheep has roughly the same probability of being eaten last. In particular the median of the distribution is 0.0204, which is incredibly close to the exact result 1/49~0.020408. The histogram becomes even more uniform for a smaller N and more simulations (second plot below).
Final remarks
This problem is a classical example of the complexity and elegance of probabilistic thinking probed during quantitative finance interviews. By leveraging symmetry, conditional probabilities, and classical problems like the Gambler’s Ruin, we were able to derive a precise answer that complements our intuition, and confirmed it through simulations.
Mastering such problems is crucial for aspiring quants as it builds a robust foundation for real-world financial challenges. Each solved problem enhances your analytical skills, bringing you closer to mastering all the important concepts. Keep practicing, stay curious, and embrace the challenges. Stay tuned for more fully solved and explained quant problems on my medium page!
