Expected Number of Surviving Sharks
100 sharks are arranged in a line. Each shark has a distinct, random speed. A faster shark eats any adjacent slower shark it encounters. This process continues until no more eating is possible.
What is the expected number of sharks remaining?
Generalize to $n$ sharks.
Hints
- Think about what it means for a shark to survive. It must be faster than every shark that can threaten it. In the adjacent-eating model, which sharks threaten shark $i$?
- Use indicator variables: let $I_i = 1$ if shark $i$ survives. What is $P(I_i = 1)$ for an interior shark? Consider the relative ranking of shark $i$ and its two neighbors.
- Among three randomly ranked neighbors, the probability the middle one is the largest is /3$. Edge sharks only compete with one neighbor, so their survival probability is/2$. Apply linearity of expectation.
Worked Solution
How to Think About It: The trick is figuring out which sharks survive. A shark survives if and only if no faster shark can reach it by eating through a chain of slower sharks between them. In the standard formulation, a shark survives if it is faster than all sharks to its left (or equivalently, if it is a left-to-right record). But the most common interview version uses the "local maximum" model: a shark survives if it is faster than both its immediate neighbors (since each shark only eats adjacent sharks, and the process resolves locally).
The right model depends on the exact eating rules, but the local-maximum version is the most commonly asked. Let's solve that one.
Quick Estimate: For a random permutation of $n$ elements, the probability that element $i$ is a local maximum (greater than both neighbors) is
/3$ for interior elements. Edge elements only need to beat one neighbor, so they survive with probability/2$. For $n = 100$: $E \approx 2 \times 1/2 + 98 \times 1/3 = 1 + 32.67 \approx 33.67$. So roughly one-third of the sharks survive.\leq i \leq n-1$): Shark $i$ survives iff it is faster than both neighbors. Among any three distinct values, each is equally likely to be the largest, so:Approach: Use linearity of expectation with indicator variables for each shark's survival.
Formal Solution: Assign speeds as a uniformly random permutation of $\{1, 2, \ldots, n\}$. Let $I_i = 1$ if shark $i$ survives.
Interior sharks (
$P(I_i = 1) = \frac{1}{3}$
Edge sharks ($i = 1$ or $i = n$): Shark $i$ survives iff it is faster than its single neighbor. Among two distinct values, each is equally likely to be the larger:
$P(I_1 = 1) = P(I_n = 1) = \frac{1}{2}$
By linearity of expectation:
$E[\text{survivors}] = \sum_{i=1}^{n} P(I_i = 1) = 2 \cdot \frac{1}{2} + (n-2) \cdot \frac{1}{3} = 1 + \frac{n-2}{3} = \frac{n+1}{3}$
For $n = 100$:
$E[\text{survivors}] = \frac{101}{3} \approx 33.67$
Answer: The expected number of surviving sharks is $\dfrac{n+1}{3}$. For $n = 100$, this is $\dfrac{101}{3} \approx 33.67$.
Note: If the eating rule instead says that each faster shark eats *all* reachable slower sharks (not just adjacent), then a shark survives iff it is a left-to-right maximum, and the expected number of survivors is $H_n = \sum_{k=1}^n 1/k \approx \ln n + \gamma$. For $n = 100$ this would be about $5.19$. The problem statement ("adjacent") points to the local-maximum model with answer $(n+1)/3$.
Intuition
This problem showcases two of the most powerful tools in discrete probability: indicator variables and symmetry. Instead of simulating the chaotic eating process, you sidestep it entirely by asking the right question for each shark individually. The local-maximum condition reduces a dynamic process to a static one -- you don't need to simulate the order of eating, just check a local condition on the initial permutation.
The
/3$ probability for interior elements is a beautiful consequence of exchangeability: among any three distinct values, each is equally likely to be the maximum. This same argument appears in problems about records, local extrema in random walks, and peak-counting in permutations. The general lesson: when a survival condition depends only on the relative order of a small number of neighbors, exploit the uniform distribution over rankings to get exact probabilities without any computation.