Should The Grizzly Bear Eat The Salmon?

A grizzly bear stands in the shallows of a river during salmon spawning season. Precisely once every hour, a fish swims within its reach. The bear can either catch the fish and eat it, or let it swim past to safety. This grizzly is, as many grizzlies are, persnickety. It’ll only eat fish that are at least as big as every fish it ate before.

Each fish weighs some amount, randomly and uniformly distributed between 0 and 1 kilogram. (Each fish’s weight is independent of the others, and the skilled bear can tell how much each weighs just by looking at it.) The bear wants to maximise its intake of salmon, as measured in kilograms. Suppose the bear’s fishing expedition is two hours long. Under what circumstances should it eat the first fish within its reach? What if the expedition is three hours long?

The Riddler, FiveThirtyEight(original post)

Solution

Start with the two-hour decision. If the bear eats the first fish of weight $x$, it may also take the second when that one is heavier, for an expected haul of $x + \int_x^1 t\,dt = x + \tfrac12(1-x^2)$. If instead it lets the first fish pass, it has eaten nothing, so the second fish is fair game whatever its size, worth $\tfrac12$ on average. Eating wins by $$x + \tfrac12(1-x^2) - \tfrac12 = x - \tfrac{x^2}{2} = \tfrac{x}{2}(2 - x) \ge 0$$ for every $x$ in $[0,1]$. So the bear should always eat the first fish. The same comparison applies at every hour: taking a fish you are allowed to take only adds weight now, and the cost (a higher bar later) never outweighs it. The greedy rule, eat every fish that matches or beats all you have eaten, is optimal, and in particular the first fish always goes down.

Now the expected haul under that rule. Let $Y_i$ be the weight eaten in hour $i$; the bear eats then only if $X_i$ exceeds the running maximum $M_{i-1} = \max(X_1,\dots,X_{i-1})$, in which case $Y_i = X_i$. Given $M_{i-1} = m$, $$\mathbb{E}[Y_i \mid M_{i-1}=m] = \int_m^1 t\,dt = \tfrac12(1 - m^2).$$ The maximum of $i-1$ uniforms has density $(i-1)m^{i-2}$, so $\mathbb{E}[M_{i-1}^2] = (i-1)/(i+1)$ and $$\mathbb{E}[Y_i] = \tfrac12\Big(1 - \tfrac{i-1}{i+1}\Big) = \frac{1}{i+1}.$$ Summing, the expected catch is $\tfrac12 + \tfrac13 = \boxed{\tfrac{5}{6}}$ kilograms over two hours and $\tfrac12 + \tfrac13 + \tfrac14 = \boxed{\tfrac{13}{12}}$ kilograms over three.

The computation

Play out the greedy bear: draw the hourly weights, eat each fish that is at least as heavy as every fish eaten so far, and average the total over many expeditions of two and of three hours.

import numpy as np
rng = np.random.default_rng(0)
def expected_haul(hours, runs=2_000_000):
    W = rng.random((runs, hours))
    total = 0.0
    for row in W:
        bar = 0.0; got = 0.0
        for w in row:
            if w >= bar:                 # at least as big as all eaten so far
                got += w; bar = w
        total += got
    return total / runs
print(expected_haul(2))                  # ~0.8333 = 5/6
print(expected_haul(3))                  # ~1.0833 = 13/12