11
$\begingroup$

Suppose you want to go fishing at the nearby lake from 8AM-8PM. Due to overfishing, a law has been instated that says you may only catch one fish per day. When you catch a fish, you can choose to either keep it (and thus go home with that fish), or throw it back into the lake and continue fishing (but risk later settling with a smaller fish, or no fish at all). You want to catch as big a fish as possible; specifically, you want to maximize the expected mass of fish you bring home.

Formally, we might set up this problem as follows: fish are caught at a certain rate (so, the time it takes to catch your next fish follows a known exponential distribution), and the size of caught fish follows some (also known) distribution. We want some decision process which, given the current time and the size of a fish you just caught, decides whether to keep the fish or throw it back.

So the question is: how should this decision be made? Is there some simple (or complicated) way of deciding when to stop fishing? I think the problem is equivalent to determining, for a given time t, what expected mass of fish an optimal fisher would take home if they started at time t; the optimal decision process would keep a fish if and only if the fish is heavier than that expected mass. But that seems sort of self-referential; we're defining the optimal fishing strategy in terms of an optimal fisher, and I'm not quite sure how to proceed.

$\endgroup$
15
  • 6
    $\begingroup$ Check out the secretary problem on Wikipedia - specifically the section on the 1/e-law of best choice. $\endgroup$
    – soakley
    Commented Jul 30, 2018 at 19:16
  • 2
    $\begingroup$ I think a key difference here is that it is assumed we know how everything is distributed, whereas the key to that solution is that it uses the first 1/e applicants just to gain some of that knowledge and define a good threshold. I think a similar idea couldn't quite work here. You could imagine just deriving a threshold from the distributions, but I don't think it should be fixed; I think the threshold should decrease over time, as you have less and less time to catch better/any fish. $\endgroup$
    – b2coutts
    Commented Jul 30, 2018 at 19:25
  • 1
    $\begingroup$ @soakley see also my response to olooney's answer; the (expected) value of waiting depends not only on what catches you'll get in the future, but which of those catches your strategy will actually take. So I think there's a weird self-referential aspect to this question as well. $\endgroup$
    – b2coutts
    Commented Jul 30, 2018 at 21:19
  • 1
    $\begingroup$ What is the function or value that we try to optimize? That is, how do we weigh the risk and profit? Is the point to come up with a method that maximizes the expectation value of the caught fish size? Are we just fishing one day or multiple days, and in the latter case how are days correlated? $\endgroup$ Commented Feb 20, 2019 at 13:26
  • 1
    $\begingroup$ We know the distribution... does that just refer to the type of distribution, or does that also include the distribution parameters? $\endgroup$ Commented Feb 20, 2019 at 14:38

1 Answer 1

5
$\begingroup$

Let $\lambda$ denote the rate of the Poisson process and let $S(x)=1-F(x)$ where $F(x)$ is the cumulative distribution function of the fish size distribution.

Let $t=0$ denote the end of the day and let $g(t)$, $t\le 0$, denote the expected catch in the interval $(t,0)$ we obtain if using the optimal strategy. Clearly $g(0)=0$. Also, if we catch a fish of size $x$ at time $t$ we should keep it and stop fishing if it is larger then $g(t)$. So this is our decision rule. Thus, a realisation of the process and the realised decision (green point) may look as follows:

enter image description here

Working in continuous time, using ideas from stochastic dynamic programming, the change in $g(t)$ backwards in time is described by a simple differential equation. Consider an infinitesimal time interval $(t-dt,t)$. The probability that we catch a fish of size $X>g(t)$ in this time interval is $$ \lambda dt S(g(t)), $$ otherwise our expected catch will be $g(t)$.

Using a formula for mean residual life, the expected size of a fish larger than $g(t)$ is $$ E(X|X>g(t))=g(t)+\frac1{S(g(t))}\int_{g(t)}^\infty S(x)dx. $$

Hence, using the law of total expectation, the expected catch in the interval $(t-dt,0)$ becomes $$ g(t-dt) =[\lambda dt S(g(t))][g(t)+\frac1{S(g(t))}\int_{g(t)}^\infty S(x)dx] + [1-\lambda dt S(g(t)] g(t). $$

Rearranging, we find that $g(t)$ satisfies $$ \frac{dg}{dt}=-\lambda \int_{g(t)}^\infty S(x) dx. \tag{1} $$ Note how $g(t)$ towards the end of the day decline at a rate equal to the product of the Poisson rate $\lambda$ and the mean fish size $\int_0^\infty S(x)dx$ reflecting that we at that point will be best off keeping any fish we might catch.

Example 1: Suppose that the fish sizes $X\sim \exp(\alpha)$ such that $S(x)=e^{-\alpha x}$. Equation (1) then simplifies to $$ \frac{dg}{dt}=-\frac\lambda\alpha e^{-\alpha g(t)} $$ which is a separable differential equation. Using the above boundary condition, the solution is $$ g(t) = \frac1\alpha\ln(1-\lambda t), $$ for $t\le 0$ shown in the above Figure for $\alpha=\lambda=1$. The following code compares the mean catch using this strategy computed based on simulations with the theoretical mean $g(-12)$.

g <- function(t,lambda, rate) {
  1/rate*log(1-lambda*t)
}
catch <- function(daylength=12, lambda=1, rfn=runif, gfn=g, ...) {
  n <- rpois(1,daylength*lambda)
  starttime <- -daylength
  arrivaltimes <- sort(runif(n,starttime,0))
  X <- rfn(n,...)
  j <- match(TRUE, X > gfn(arrivaltimes,lambda,...))
  if (is.na(j))
    0
  else
    X[j]
}
nsim <- 1e+5
catches <- rep(0,nsim)
for (i in 1:nsim)
  catches[i] <- catch(gfn=g,rfn=rexp,rate=1,lambda=1)
> mean(catches)
[1] 2.55802
> g(-12,1,1)
[1] 2.564949

Example 2: If $X \sim U(0,1)$ a similar derivation leads to $$ g(t) = 1 - \frac1{1-\lambda t/2} $$ as the solution of (1). Note how $g(t)$ tends to the maximum fish size as $t\rightarrow -\infty$.

$\endgroup$
3
  • 3
    $\begingroup$ It's not clear why the strategy of stopping if you catch a fish whose size exceeds $g(t)$, is optimal. It would make more sense to stop if the fish size exceeds the expected maximum fish size in $(t,0)$. $\endgroup$
    – Alex R.
    Commented Nov 6, 2018 at 23:10
  • 1
    $\begingroup$ You'll stop fishing before you have a chance to choose the largest fish. $g(t)$ is the expected size of the fish you decide to keep caught in the interval $(t,0)$. It's also the decision rule, at time $t$, stop fishing if you catch a fish larger than $g(t)$. $\endgroup$ Commented Nov 6, 2018 at 23:13
  • 1
    $\begingroup$ @AlexR. I tried a simulation for example 2 using the expected maximum fish size $$g'(t)=1-\frac{e^{\lambda t}-1}{\lambda t}$$ It is close but worked less good. The expectation of the maximum includes fish which will not get picked (those that turn out to be less than $g'(t)$). With this expectation of the maximum, you are more inclined to wait until that moment that you get a very advantageous catch. This gives you more often big fish, but at the cost of more smaller fish, or none at all. $\endgroup$ Commented Feb 21, 2019 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.