Payoff of drawing card

Question

You have 100 cards with face value 1-100, randomly shuffled in a bag. Your payoff is the face value (in dollar) of the last card you draw. You can draw as many time as you want (with replacement), but each time you draw, it costs 1 dollar. What would be the best strategy to play this game? Does this game has a analytical solution?

Answer 1

Clearly you should draw the first card, as your expected profit is $49.5$. After the first card, your strategy is to quit whenever you draw a card higher than $n$ and draw on $n$ or less. The question is what $n$ should be. Clearly it should be at least $49$.

Having chosen $n$, your average accepted card is $\frac {101+n}2$. The chance of drawing an acceptable card is $\frac {100-n}{100}$. The expected number of cards you will draw is

$1\left(\frac {100-n}{100}\right) +2\left(\frac {100-n}{100}\right)\left( \frac n{100}\right)+3\left(\frac {100-n}{100}\right)\left( \frac n{100}\right)^2+4\left(\frac {100-n}{100}\right)\left( \frac n{100}\right)^3+\ldots=\left(\frac {100-n}{100}\right) \left(1+\sum_{k=1}^\infty (k+1)\left(\frac k{100}\right)^k \right)=\left(\frac {100-n}{100}\right) \left( \frac 1{(1-\frac n{100})^2}\right)$

Our expected profit if we draw is then $$\frac {101+n}2-\left(\frac {100-n}{100}\right) \left( \frac 1{(1-\frac n{100})^2}\right)=\frac {101+n}2-\frac {100}{100-n}$$

Searching for the maximum finds it at $n=100-10\sqrt {2}\approx 85.8579$ As we must have $n$ an integer, we try $85$ and $86$, finding the maximum at $n=86$ with value $\frac {1209}{14} \approx 86.357$. You should draw any time your card is $86$ or less. As a sanity check, your average accepted card will be $93.5$ and it should take about $\frac {100}{14} \approx 7.14$ draws to get one, so the profit is reasonable.

An easier approach is to define $G(n)$ as the gain at $n$ andlook for the $n$ were $G(n+1)-G(n)$ turns negative. This is $$G(n+1)-G(n)=\frac 12-\frac {100}{99-n}+\frac {100}{100-n}$$ which turns negative at about $n=85.349$, so we should increment from $n=85$ to $n=86$ but not further.

Answer 2

here's what my simulation got

https://dotnetfiddle.net/lie2h4

quit on 87 yields expected £86.532

quit on 85 yields expected £86.3432

quit on 86 yields expected £86.2902

quit on 88 yields expected £86.2602

quit on 89 yields expected £86.2053

quit on 84 yields expected £86.0106

quit on 83 yields expected £85.9269

quit on 90 yields expected £85.7383

quit on 82 yields expected £85.6761

quit on 91 yields expected £85.6596

quit on 81 yields expected £85.6201

quit on 80 yields expected £85.1205

quit on 79 yields expected £85.0571

quit on 92 yields expected £85.0558

.....

quit on 4 yields expected £51.0134

quit on 3 yields expected £50.1926

quit on 2 yields expected £50.1084

quit on 99 yields expected £49.7115

quit on 1 yields expected £49.6166

quit on 100 yields expected £1.1244

Answer 3

Denote by $\xi$ the expected gain per game under optimal strategy. Then $\xi$ is a solution of the equation $$x=\sum_{k=1}^{100}{1\over 100}\>\max\{k,x\}\ -1\ ,\tag{1}$$ because one will reject the first drawn number $k$ if continuing to draw seems more promising, and will accept $k$ otherwise. The function $$f(x):=\sum_{k=1}^{100}{1\over 100}\>\max\{k,x\}\ -1$$ is increasing, continuous, and has derivative $f'(x)=\lfloor x\rfloor/100<1$ for noninteger $x$. Furthermore $f(0)=49.5>0$ and $f(100)=99<100$. It follows that $(1)$ has exactly one solution $\xi\in\>]0,100[\>$. Plotting $f$ shows that in fact $86<\xi<87$. We therefore write $\xi=86+\tau$ with $0<\tau<1$, and solve $$86+\tau=\sum_{k=1}^{86}{86+\tau\over 100}+\sum_{k=87}^{100}{k\over 100}\ -1$$ for $\tau$. The result is $\tau={5\over14}$, so that $\xi=86.3571$.

The optimal strategy therefore turns out to be the following: Keep drawing until you get a number $\geq87$. The expected gain per game then is $86{5\over14}$.