Leftwards Jump
A Probability question asked in Junior Quant interview at Jane Street
A frog is hopping between 8 lily pads labeled 1 through 8 from left to right. The frog starts on lily pad 1. At each turn, the frog hops to a lily pad that it has not been to yet. Find the probability the frog made exactly 1 leftwards hop after visiting all of the stones
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
The frog must hop 7 times to visit all of the lily pads, so there are 7! ways it can move. Consider the set S = {2, 3, 4, 5, 6, 7, 8}. These are the unvisited vertices of the frog. Some arrangement where the frog makes exactly one leftwards, hop is exactly the same as asking how many ways we can partition S into two subsets, say A and B, where the frog hops from 1 to all of the lily pads in A, ordered from left to right and then all of the lily pads in B left to right. For example, let A = {2, 3, 6, 7} and B = {4, 5, 8}. The frog would then hop in the order
However, we have to be careful here, as if either B is empty or the entire set {2, 3, 4, 5, 6, 7, 8}, no left hop occurs. However, there are other cases as well. Namely, to not left hop, the set A must contain elements such that max(A) < min(B). This occurs exactly when A contains the starting sequence of the elements. This would mean we exclude
(we already excluded the full set). This adds 6 additional sets we must exclude. Therefore, we must remove 8 elements from the 2^7 = 128 possibilities of how we can create the subsets. Therefore, our answer is
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!