Deciding when to stop searching for a new type of shell on a beach? Suppose I am on the beach looking for shells. I am interested in finding as many different types of shell as possible, rather than shells themselves.
Assuming $T_1, T_2, \dots$ are the types of shell $1, 2,$ etc, and $C_i = |\{T_j: j \le i\}|$ is the number of types of shells for shells $1, 2, \dots j$.
How might I model $C_i$ and assuming a suitable model, when should I stop searching because the number of new shells I need to pick up to be likely to find a new types becomes very large. Is there some code to implement this.
Thoughts:

*

*I think it would make sense to represent the types of shell as some sort of power law. So we have shell types $S_1, S_2\dots$ such that $P(T=S_j) = k r^j$. Is there a more natural distribution for shell types.

*We might have finite set of types $S_1, S_2, \dots S_n$ with a power law distribution. It would be nice to find the $n$ that maximizes the likehood of our observations.

*I think the result for this might like inside https://en.wikipedia.org/wiki/Search_theory or https://en.wikipedia.org/wiki/Optimal_stopping.

 A: $\newcommand{\R}{\mathbb R}\newcommand{\T}{\mathcal T}$There would be no reason for you to ever stop searching unless you would have to incur a cost/penalty with each new observation/trial.
Suppose, for simplicity, that this cost is a real constant $c>0$, for each observation. Let $[k]:=\{1,\dots,k\}$ be the (say finite) set of the types of shells. Let $U\colon[k]\to\R$ be a utility function such that, for each $j\in[k]$, $U(j)$ is the utility of having exactly $j$ types of shells.
Let $T_1,T_2,\dots$ be the types of shells obtained on trials $1,2,\dots$. Assume that the $T_i$'s are iid random variables with values in $[k]$. For $J\subseteq[k]$, let
\begin{equation}
    p_J:=P(T_1\in J). 
\end{equation}
For natural $n$, consider the random subset
\begin{equation}
    \T_n:=\{T_i\colon i\in[n]\} 
\end{equation}
of $[k]$, so that $|\T_n|$ is the number of (distinct) types of shells obtained on trials $1,\dots,n$.
Then our expected gain after $n$ trials is
\begin{equation}
    G_n:=EU(|\T_n|)-cn,
\end{equation}
which is the expected utility obtained on trials $1,\dots,n$ minus the cost of the $n$ trials. We want to stop at a time moment $n$ maximizing the expected gain $G_n$.
Let us explicitly express the expected gain $G_n$ in terms of the distribution of $T_1$, that is, in terms of the probabilities $p_J$. To do so, consider the events
\begin{equation}
    A_J:=\{\T_n=J\},\quad B_J:=\{\T_n\subseteq J\}
\end{equation}
for $J\subseteq[k]$. Then $A_J=B_J\setminus\bigcup_{j\in J}B_{J\setminus\{j\}}$ and hence
\begin{equation}
    P(A_J)=P(B_J)-P\Big(\bigcup_{j\in J}B_{J\setminus\{j\}}\Big). 
\end{equation}
Noting that $P(B_J)=p_J^n$ and expressing $P\Big(\bigcup_{j\in J}B_{J\setminus\{j\}}\Big)$ by the inclusion-exclusion, we get
\begin{equation}
    P(A_J)=\sum_{r=0}^{|J|} (-1)^{|J|-r}\sum_{R\in\binom Jr} p_R^n,
\end{equation}
where $\binom Jr$ denotes the set of all subsets of $J$ of cardinality $r$.
Next, for $j\in[k]$,
\begin{equation}
    P(|\T_n|=j)=\sum_{J\in\binom{[k]}j}P(A_J). 
\end{equation}
Thus,
\begin{equation}
\begin{aligned}
    G_n&=-cn+\sum_{j=0}^k U(j)P(|\T_n|=j) \\ 
    &=-cn+\sum_{j=0}^k U(j)\sum_{J\in\binom{[k]}j}\sum_{r=0}^j (-1)^{j-r}\sum_{R\in\binom Jr} p_R^n.  
\end{aligned}
\end{equation}

Assuming (say) some kind of parametric model for the distribution of $T_1$, one can estimate the probabilities $p_J$ based on a comparatively small sample of shells and then estimate $G_n$ for all $n$. Alternatively, one may be successively updating the estimates of the $p_J$'s with each new trial.

Below is the image of a Mathematica notebook with calculations of $G_n$ for $k=10$, $P(T_1=j)\propto0.6^j$ and $U(j)=\ln(2+j)$ for $j\in[k]$, and $c\in\{0.05,0.1,0.2\}$. It appears that the sequence $(G_1,G_2,\dots)$ has an increasing-decreasing pattern, with maximum attained at $n=2$ for $c=0.2$, at $n=3$ for $c=0.1$, and at $n=6$ for $c=0.05$. (Click on the image to magnify it.)

A: *

*The Good-Turing estimator addresses a very similar problem.

The model is that there is an unknown number of types $n$ and a probability distribution $p \in \Delta_n$. Each time you pick up a new shell, it is sampled independently from $p$. After $m$ samples, you can ask for the "probability" that a new sample will be of a hitherto-unseen type.


*I agree with the comment that the coupon collector problem is highly related. The model is the same as described above, but we are asked to bound the stopping time (number of samples $m$) after which all types have been seen. Usually, we assume $p$ is the uniform distribution. In this case, the expected number of samples turns out to be roughly $n \log n$. Your question has a twist that we don't know $n$, so we have to do a reverse kind of calculation.


*I would model your problem as above, and I would assume a confidence parameter $\delta$ is given. The problem is to define a stopping rule such that, for any $n$, the probability that there is still an undiscovered type when we stop is at most $\delta$. This would assume the uniform distribution.
I don't think the optimal solution is obvious, but my first thought is related to Good-Turing. I start drawing samples. At any time $t$, suppose I've seen $n_t$ different types so far and there have been $k_t$ samples since I last saw a new type. If there were at least one undiscovered type, then the chance of it coming up would have been at least $1/(n_t+1)$ on each of those trials, so a total chance of $p_t := \left(\frac{n_t}{n_t+1}\right)^{k_t} \leq e^{-k_t / (n_t + 1)}$ of having this many samples without a new observation.
So if we ever see at least $(n_t + 1) \ln(1/\delta)$ samples in a row without a new type (where $n_t$ is the number of types we've seen so far), we should be able to stop and conclude with confidence $1-\delta$ that we've seen all the types.


*If we don't assume the distribution is uniform, then I think you can probably modify the above to make a stopping rule of the following form: If we stop, then with confidence $1-\delta$, the total probability on unseen types is at most $\epsilon$. What I mean by confidence is that for any $n$, any $p \in \Delta_n$, and any set of types with $p$-mass at most $\epsilon$, the probability that your procedure stops before seeing one of those types is at most $\delta$. In fact, I think the new rule is to stop once we see $\frac{1}{\epsilon} \ln(1/\delta)$ samples in a row with no new types.


*The problem is not very related to the optimal stopping or search theory problems I have seen.
