1 Leftward Jump

Every order of visiting stones $2, \dots, 7$ is equally likely. Why? Work out the probability of one specific order, then of another.

A route with exactly one left hop goes up, drops once, then goes up again. Build such a route by asking each stone whether it is in the first or the second increasing group. How many ways is that, and which of them give no left hop at all?

Step 1: Every visiting order is equally likely. The frog visits stones $2, \dots, 7$ in some order, and there are $6! = 720$ possible orders. Take one, say $3, 5, 6, 2, 4, 7$. Its probability is the product of the chances of each choice:

• 1st hop: $6$ unvisited stones, it picks $3$: chance $\tfrac16$;
• 2nd hop: $5$ left, it picks $5$: chance $\tfrac15$;
• then $\tfrac14$, $\tfrac13$, $\tfrac12$ and finally $1$.

So this route has probability $\tfrac16 \cdot \tfrac15 \cdot \tfrac14 \cdot \tfrac13 \cdot \tfrac12 \cdot 1 = \tfrac{1}{720}$. Any other order has the same number of choices at each hop ($6, 5, 4, 3, 2, 1$), so it also has probability $\tfrac{1}{720}$. All $720$ orders are equally likely, and

Step 2: What one left hop looks like. The hop from stone $1$ always goes right. After that, a hop goes left exactly when the next stone is smaller than the current one. So a route with exactly one left hop goes up, drops once, then goes up again, such as

where $6 \to 2$ is the only left hop.

Step 3: Build these routes by splitting the stones into two groups. Ask each of the stones $2, 3, 4, 5, 6, 7$ one question: are you in the first group or the second group? Then visit the first group in increasing order, followed by the second group in increasing order.

• Each stone has $2$ answers and there are $6$ stones, so there are $2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^6 = 64$ ways to split.
• For example, first group $\{3, 5, 6\}$ gives the route $3, 5, 6, 2, 4, 7$.
• The groups don't need to be the same size, and either one can be empty.

Every route with exactly one left hop is made this way exactly once: its first group is the stones before the drop. So nothing is counted twice, and we only need to remove the splits that give no drop at all.

Step 4: Remove the splits with no drop. A split gives no drop when the first group is just the smallest stones, because then the route is $2, 3, 4, 5, 6, 7$ with no left hop:

That is $7$ splits. For example, first group $\{2\}$ gives $2 \,|\, 3, 4, 5, 6, 7$: no left hop. In every other split, some stone in the second group is smaller than the largest stone in the first group, so the route drops exactly once.

So $64 - 7 = 57$ orders have exactly one left hop.

Check with 3 stones ($2, 3, 4$): there are $2^3 = 8$ splits, and $4$ give no drop ($\{\}$, $\{2\}$, $\{2, 3\}$, $\{2, 3, 4\}$). That leaves $4$ routes: $3 \,|\, 2, 4$, then $4 \,|\, 2, 3$, then $2, 4 \,|\, 3$ and $3, 4 \,|\, 2$. Listing all $3! = 6$ orders directly agrees: $2, 3, 4$ has no left hop and $4, 3, 2$ has two.

Answer:

In general, with $n$ stones the probability is $\dfrac{2^{n-1} - n}{(n-1)!}$.