The Rabbit and the Stone Problem

I have this friend of mine, who constantly pokes me to solve interesting puzzles. He sometimes even rings me up, just to look at the problem he sent :P This is one of those problems, that I enjoyed working on. It requires understanding of basic probability theory, counting and some time to stick to a problem that interests you.

The problem goes like this…
There are 7 stones in a row labelled 1 to 7 from left to right. A rabbit starts at stone 1 and on each turn hops to a new stone that they haven’t visited yet. After visiting all the stones, what is the probability the rabbit made exactly one leftwards jump?

The rabbit starts off at stone 1 and can hop around to all the unvisited stones until all the stones are visited.

If you have been following my previous problems, you would know that dissimilar from the previous problems here we are required to find the probability of some event occurring rather than expectation of a random variable.

Unlike the 4 key points to find expectation of discrete r.v.s, there is no particular approach that always works out. But some basic ideas to try out when trying to find probability of an event are:

• Try counting based methods, where you count the number of favorable outcomes and number of possible outcomes.
• Try using simple, yet the most powerful tool, Baye’s Rule.
• A general idea which is applicable in all of Probability Theory is to try breaking the event as union of smaller solvable events. Often goes under the name of Law of Total Probability.

It’s not that, only one of the above guidelines can be used at a time. I will be using a conjunction of the counting method and law of total probability to solve this problem.

So, let’s start by defining a couple of things to facilitate framing the problem mathematically. Let A be the event(note that I didn’t say A to be a r.v.) of the rabbit visiting all stones with exactly one leftward jump. We are interested in finding probability of the event A i.e. P(A).

For the easier part of the problem, how many ways can the rabbit hop around to visit all the stones? This is same as permuting the stones in any order and the rabbit will simply visit these permuted stones from left to right. Since, the rabbit already starts from the stone numbered 1, we can permute the other 6 stones in 6! ways.

After having the total number of ways the rabbit can visit the stones without any restriction as described above. I am interested in finding out the number of cases out of the total number of ways, where the event A occurs. This sort of method is often used in the frequentist approach to compute the probability of an event. But there is a problem here, it seems complicated to calculate the number of ways in which the rabbit can visit all the stones by making only one leftward jump. That is why, I will try to find out the exhaustive set of rules that the favorable case needs to follow.

• Observe that if I want to have exactly one leftward jump, I can decompose A into mutually exclusive (because no two of the following events can happen together) parts namely A_2, A_3, …, A_6 , where A_i represents the event “reach at ith stone by left jump and no left jump anywhere else”.

All the A_i’s visualized

A is the union of mutually disjoint events A_i, A_7 is not included as we can’t reach 7th stone by left jump

• Closely observe the events A_i’s, to make it easy to understand let’s focus only on A_4 as of now. See that 2nd, 3rd and at least one of the other stones, except 4th(i.e. 5th, 6th or 7th) must be covered before reaching 4th stone.. as if 2nd or 3rd stone occurs after reaching 4th stone by left jump, then there is occurrence of another left jump (to cover 2nd or 3rd stone, which is not allowed) and if only 2nd and 3rd stone are covered before 4th, then we are reaching 4th stone by a right jump (which is not allowed in this case as we want to reach 4th stone by left jump).

The light green paths shows 2 examples of how we cannot reach 4th stone by right jump (on the upper side) and how we cannot skip a stone before 4th stone (on the lower side) which will lead to more than two left jumps. The olive path shows that there are many possibilities after 2nd stone and 3rd stone, one of these possible paths is visualized by dotted line.

• Summarizing the above discussion, A_i is equivalent to visiting 2nd, 3rd, …, (i-1)th stone in order by right jumps and then visiting at least one stone from (i+1)th stone, …, 7th stone(by right jumps) after reaching (i-1)th stone and then visiting ith stone by left jump followed by covering the rest of the stones which are not yet covered between (i+1)th stone and 7th stone by right jumps.

Phew! That was a lot. But how did I come up with this way of breaking? Cause I thought about where can I observe exactly one left jump (created events out of these individual cases) and then figured out what are the cases by which each of these smaller events can happen. It still requires bit of tinkering, but is doable compared to directly counting exactly one left jump cases.

Now, to count the number of favorable outcomes for each A_i, let f(i) be the number of favorable outcomes for A_i. As per the way described in the last bullet point, it is same as the number of ways we can select one or two or … or (7-i) stones. Then,

We can choose k=1 to 7-i stones on the right of the ith stone, which we want to reach by left jump. For each k we will get the number of ways, which we will add up. The last equality is using the identity for the sum of binomial coefficients.

The number of possible favorable outcomes for A_4 visualized.

This leads to the following probabilities of the events A_i’s using number of favorable outcomes divided by number of all outcomes.

We get the probability of each of the A_i’s

Since, these smaller events are mutually exclusive, we have,

The second equality holds as the events are mutually exclusive.

Lo and Behold! Finally we have the probability for exactly one left jump after the rabbit has visited all the stones. But wait a second? Is it trustworthy? Let’s see in the next section.

The simulation of the above rabbit and stone problem is presented below

import random

def isOneLeftJump(): # simulates one round of hopping to cover all stones and return if exactly 1 left jump occured
  stones = [stone for stone in range(2, 8)] # the stones to be visited
  prev_hop = 1 # currently at stone 1
  left_jump = 0 # counter for left jumps
  for _ in range(6): # covering the rest of the stones
    hop_idx = random.randint(0, len(stones)-1) # choosing one of the left over stones
    hop = stones.pop(hop_idx) # removing the visited stones from the list to be visited next
    if hop < prev_hop: # checking it is a left jump
      left_jump += 1 # updating counter
    prev_hop = hop # updating current stone position
if left_jump == 1: # If exactly one left jump return 1 else 0
    return 1
  else:
    return 0

N = 100000
print(f"Probability of exactly 1 left jump in {N} rounds of hopping to cover all stones: {sum([isOneLeftJump() for _ in range(N)]) / N}")

The simulation yields,

Probability of exactly 1 left jump in 100000 rounds of hopping to cover all stones: 0.0799

Ah that’s pretty close to the answer obtained.

An interesting extrapolation of the problem to a general situation with n stones will similarly result in the following probability,

Last equality by Geometric Progression Sum

Using the above result, we can verify an intuitive statement that is “if the number of stones increases, the probability of observing exactly one left jump decreases”, cause it becomes a rarer and rarer event as n increases.

Since, factorial grows faster than exponential function

Thank you for sticking around to the end of this interesting problem. You can also be like my friend to poke me with interesting puzzles on which you would like to see a detailed solution. Cool, I guess.. I should now finally pick up my friend’s call who is still ringing me to ask whether I solved his problem :P