Should The Grizzly Bear Eat The Salmon?

\newcommand\EE{\mathbb E} \newcommand\PP{\mathbb P}

Problem

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?

Solution

Let $X_i$ be the random variable denoting the weight of fish seen each hour where $i=1,2,\dots,n$ .

We have $X_i \sim \mathcal{U}(0,1)$ for $i = 1,2, \dots, n$ .

Greedy Strategy

By following the Greedy Strategy, the bear eats as much salmon as it can starting with the first salmon in the first hour.

Let $Y_i$ be the weight of the fish consumed in the $i^{th}$ hour using the greedy strategy.

We have the following equations for the greedy strategy:

\begin{aligned} Z_i &= \sum_i^n Y_i \\ Y_1 &= X_1 \\ Y_i &= X_i, \text{ if $X_i \geq \max(X_1, X_2, \dots, X_{i-1})$ and $i>1$} \end{aligned}

The distribution function and the density function of a random variable $M_{i-1} = \max(X_1,X_2, \dots, X_{i-1})$ are given by

\begin{aligned} F_{M_{i-1}}(x) = x^{i-1} \\ f_{M_{i-1}}(x) = (i-1)x^{i-2} \end{aligned}

where $X_i \sim \mathcal{U}(0,1)$ and $i=2,3, \dots,n$ .

From the above, we have

\begin{aligned} \mathbb{E}[Y_i|M_{i-1}] = \int_{M_{i-1}}^1 x_i dx_i = \frac{1}{2} - \frac{M_{i-1}^2}{2} \end{aligned}

The expectation of $M_{i-1}^2$ can be calculated as follows

\begin{aligned} \mathbb{E}[M_{i-1}^2] = \int_{0}^1 m^2 f_{M_{i-1}}(m) dm \\ = \int_{0}^1 m^2 (i-1)m^{i-2} dm = \frac{i-1}{i+1} \end{aligned}

From the above, we have

\begin{aligned} \mathbb{E}[Y_i] = \mathbb{E}[\mathbb{E}[Y_i|M_{i-1}]] \\\\ = \frac{1}{2} - \frac{1}{2}\mathbb{E}[M_{i-1}^2] = \frac{1}{2} - \frac{1}{2} \frac{i-1}{i+1} = \frac{1}{i+1} \end{aligned}

Two hour expedition

To get the average total weight of salmon consumed by bear in $2$ hours under the greedy strategy we need to calculate $\mathbb{E}[Z_2]$ .

\begin{aligned} \mathbb{E}[Z_2] = \mathbb{E}[Y_1] + \mathbb{E}[Y_2] = \frac{1}{2} + \frac{1}{3} = \frac{5}{6} \end{aligned}

Three hour expedition

To get the average total weight of salmon consumed by bear in $3$ hours under the greedy strategy we need to calculate $\mathbb{E}[Z_3]$ .

\begin{aligned} \mathbb{E}[Z_3] = \sum_{i=1}^3 \mathbb{E}[Y_i] = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{13}{12} \end{aligned}

Monte Carlo Simulation

from random import random

runs = 100000

total_weight = 0
for _ in range(runs):
    r1, r2 = random(), random()
    total_weight += r1
    if r2 > r1:
        total_weight += r2

print("Avg weight of fish consumed in 2 hrs :", total_weight/runs)

total_weight = 0
for _ in range(runs):
    r1, r2, r3 = random(), random(), random()
    total_weight += r1
    if r2 > r1:
        total_weight += r2
        if r3 > r2:
            total_weight += r3
    elif r3 > r1:
            total_weight += r3

print("Avg weight of fish consumed in 3 hrs :", total_weight/runs)

Random Tic Tac Toe

Solving Kakuro using Z3