Should the grizzly eat the salmon?

This Riddler puzzle concerns a random process and sequential decision-making.

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 maximize 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?

Here is my solution:
[Show Solution]

14 thoughts on “Should the grizzly eat the salmon?”

1. Hector Pefo says:

Very nice. Double-check f2(0), though?

2. Dmytro Taranovsky says:

While there is no closed form solution for non-small k, as the number of rounds approaches infinity, the optimal (up to an asymptotic factor of 1 for the sum) strategy approaches a closed form:
threshold = w + sqrt(2/3)*sqrt(1-w^3)/w / sqrt(k), where w is the minimum weight allowed, and k is the number of remaining rounds, except for a correction for very small w to avoid divergence; the following correction is good enough: if w<k^(-1/4) set threshold to w+k^(-1/4).

Assuming the initial minimum weight is 0 and the number of rounds is k, the approximate total sum is sqrt(2/3*k), and at time t, the threshold will be approximately (t/k)^(1/3).

1. Michael K says:

Can someone please post a solution for the less mathematically mature? Dmytro, any chance you can accept my Facebook request, I wanted to discuss some of these problems with you? Sposibo

1. Dmytro Taranovsky says:

In brief, here is my solution as the number of rounds k approach infinity.

At time t, the optimal threshold will be around (t/k)^(1/3).

Justification: As threshold increases in c times, the time to increment the threshold by ε is reduced in c^2 times, which is as desired since the benefit of extra time (if total time is flexible) to increase threshold by ε (which by optimality, should be the same for both thresholds) is proportional to threshold/sqrt(ε_increment_time). (If time is increased in c^2 times, we can reduce the threshold increment in c times and increase the number of numbers taken in c times.)

d(threshold/dt) = 1/3*t^(-2/3)*k^(-1/3)
average_threshold_increment = (threshold-last_number)/2 = 1/(2*increment_time)
average_threshold_increment = d(threshold)/dt * increment_time
Thus,
1/(2*increment_time^2) = d(threshold)/dt,
increment_time = sqrt(1/(2*d(threshold)/dt) = sqrt(3/2)*t^(1/3)*k^(1/6)
(*) total_sum = integral(threshold/increment_time,t,0,k) = integral(sqrt(2/3)/sqrt(k),t,0,k) = sqrt(2/3*k).
Let the current number be w.
t = w^3*k
threshold – w = 1/increment_time = sqrt(2/3)*t^(-1/3)*k^(-1/6) = sqrt(2/3)/w/sqrt(k)
Let k_r be the remaining number of rounds.
k = k_r/(1-w^3)
(*) threshold = w + sqrt(2/3)*sqrt(1-w^3)/w / sqrt(k_r), except for a correction for very small w to avoid unreasonable thresholds; the following correction is good enough: if w<k_r^(-1/4) set threshold to w+k_r^(-1/4).

2. Austin Shapiro says:

Here is a simple explicit strategy that achieves O(sqrt(n)), albeit with a lower-than-optimal constant:

Divide the meal into sqrt(n) “courses” of sqrt(n) fish each. (I’ll just assume sqrt(n) is an integer; otherwise, one can make some minor adjustments that don’t affect the asymptotics.) During the kth “course”, let the bear eat any fish he can of weight less than k/sqrt(n). As a result, if at least one fish of weight between (k-1)/sqrt(n) and k/sqrt(n) appears during the kth course, then the bear will certainly eat at least one such fish during that course. The probability that a fish in that range appears during the kth course is approximately 1-1/e, since the number of such fish is roughly Poisson-distributed — pun noted — with a mean of 1. Thus, the bear’s expected consumption is approximately bounded below by (1-1/e)(1+2+3+…+(n-1))/sqrt(n), which is O(sqrt(n)). I say “bounded below” because this analysis does not account for the possibility that the bear gets to eat more than one fish during the kth course, or gets to eat a fish lighter than (k-1)/sqrt(n) during the kth course. These possibilities improve the expected consumption by some constant factor which I am too lazy to work out.

1. Austin Shapiro says:

Oops, typo: (1-1/e)(1+2+3+…+(n-1))/sqrt(n) should have been (1-1/e)(1+2+3+…+(sqrt(n)-1))/sqrt(n).

1. very cool, thanks!

btw $\LaTeX$ works in the comments with standard syntax, and I think you should also be able to edit your own posts if you want to make a correction.

3. You can also put a bound on the order of growth of the best case by noting that the most salmon the bear can eat is the length of the longest increasing subsequence, which is known to have an expected value of 2*sqrt(n) – in other words, if the bear knew the weight of all future salmon, his best case would be O(sqrt(n)), which the strategy above achieves (albeit not with the same coefficient).

Here’s an extension I suggested to Ollie that you might enjoy: suppose there are 2 bears, alpha and beta. They’re each greedy, and want to eat any salmon bigger than they’ve eaten before, but alpha-bear always gets first choice. Which bear ends up with more? (Hint: it’s not always alpha!)

4. Jim Crimmins says:

Easy way to see it’s a harmonic series for greedy case. Probability that fish N is the maximum weight fish in a sequence of N fish = 1/N. Expected weight of the maximum weight fish out of N fish for IID uniformly [0,1] distributed weights= N/N+1. So expected amount eaten at step N = 1/N * N/N+1 = 1/N+1.

1. Very nice! Linearity of expectation wins again!

5. hypergeometric says:

Very nice solution!
Did you mean to write $f’_{k+1}(t)$ rather than $f’_{k+1}(x)$ ?