The last arrivals problem that I discussed in 18.5 is similar to the famous Secretary Problem that is addressed in the Part II course Optimization and Control. In that problem the task is sequentially to interview $n$ secretaries for a job, stop & hire one who has the quality of better than any previously interviewed, and then find that choice remains better than any others that could be subsequently interviewed. This is one example of an interesting problem at the interface of probability and optimization.
The problem in 18.5 is slightly different because the number of gold coins is completely unknown. This problem has been studied by F. Thomas Bruss and Marc Yor in Stochastic Processes with Proportional Increments and The Last-Arrival Problem, Stochastic processes and their Applications, 122:3239–3261, 2012.
A game version of the problem is addressed by Johan Wästlund in the paper When only the last one will do. He discusses the following discrete game.
There is a deck of $d$ cards, and at the start of the game a devil labels the face side of some of them. There must be at least one labelled card, and at most $N$. The deck is then shuffled and the cards are turned up one by one. The selector (John), knowing $d$ and $N$, must select online the last labelled card.
The devil’s strategy is simply a probability distribution on $\{1,\dotsc, N\}$. Wästlund shows that, as $N\to\infty$, John's success probability will be about 0.352917000207196 (which is $<1/e=0.367879$).
It might be fun to find the answer for $d=52$ and $N=2$. The devil marks either 1 or 2 cards, with probabilities $p$ and $1-p$, respectively, and John will stop at the first marked card if it occurs $k+1$ or deeper in the deck of cards, or if it is the $k$th card he will stop w.p. $\theta$. Otherwise he continues, hoping to find a second marked card. What are optimal $p$, $k$ and $\theta$?
Answer: I couldn't resist figuring this out after lunch today. Both players in this game use mixed strategies. The devil will choose $p=52/103$ and John will stop if he finds the first marked card as the $21$st or deeper; if it is $20$th card then he will stop with probability $\theta=28/115$. His success probability is $927/1495\approx 0.62$.
A student suggested at the end of the lecture that we might consider a game in which our task is to stop at the point that only finitely many gold coins remain to be found. I'm not sure how we set up the problem so as to initially distribute an infinite number of gold coins in the early part of the road. But it would be certainly be interesting to ask how we might stop so as to maximize the probability that we have found all but exactly $k$ coins, generalizing the original problem, which was the case $k=0$.
The problem in 18.5 is slightly different because the number of gold coins is completely unknown. This problem has been studied by F. Thomas Bruss and Marc Yor in Stochastic Processes with Proportional Increments and The Last-Arrival Problem, Stochastic processes and their Applications, 122:3239–3261, 2012.
A game version of the problem is addressed by Johan Wästlund in the paper When only the last one will do. He discusses the following discrete game.
There is a deck of $d$ cards, and at the start of the game a devil labels the face side of some of them. There must be at least one labelled card, and at most $N$. The deck is then shuffled and the cards are turned up one by one. The selector (John), knowing $d$ and $N$, must select online the last labelled card.
The devil’s strategy is simply a probability distribution on $\{1,\dotsc, N\}$. Wästlund shows that, as $N\to\infty$, John's success probability will be about 0.352917000207196 (which is $<1/e=0.367879$).
It might be fun to find the answer for $d=52$ and $N=2$. The devil marks either 1 or 2 cards, with probabilities $p$ and $1-p$, respectively, and John will stop at the first marked card if it occurs $k+1$ or deeper in the deck of cards, or if it is the $k$th card he will stop w.p. $\theta$. Otherwise he continues, hoping to find a second marked card. What are optimal $p$, $k$ and $\theta$?
Answer: I couldn't resist figuring this out after lunch today. Both players in this game use mixed strategies. The devil will choose $p=52/103$ and John will stop if he finds the first marked card as the $21$st or deeper; if it is $20$th card then he will stop with probability $\theta=28/115$. His success probability is $927/1495\approx 0.62$.
A student suggested at the end of the lecture that we might consider a game in which our task is to stop at the point that only finitely many gold coins remain to be found. I'm not sure how we set up the problem so as to initially distribute an infinite number of gold coins in the early part of the road. But it would be certainly be interesting to ask how we might stop so as to maximize the probability that we have found all but exactly $k$ coins, generalizing the original problem, which was the case $k=0$.
