0
$\begingroup$

I'm looking for an optimal strategy as well as the derivation of this strategy for a simple game.

The game

  1. Let there be $N$ white balls and one black ball in a pouch.
  2. Upon entering the game, the player pays an entry fee $c_e$.
  3. The player makes a decision:
    • end the game $\rightarrow$ the player collects all the gained rewards and the game ends. Therefore, the player has won the sum of these rewards minus $c_e$ (which she paid before the game started).
    • continue
  4. The player draws one ball from the pouch, randomly.
    • If the ball is white, she gains a reward $c_i$ where $i$ is the number of the round. Repeat from step 3.
    • If the ball is black, the player loses all the gained reward and the game ends. Therefore, the player has won nothing and lost the entry fee $c_e$ (which she paid before the game started).

All parameters - $N$, $c_e$, $c_i$ for each $i$ - are known to the player.

The strategy (i.e. the merit of this question)

I would like to construct a strategy (i.e. a mapping from the game state to the decision whether continue/end) which maximizes the expected total winnings from the game. What is such strategy and how to derive it? Possible de-generalization is that all $c_i$ are equal.

Note: it's not a homework question, I actually want to conduct this game and would like to know some properties of it but I'm not very good at probability and statistics.

$\endgroup$
  • $\begingroup$ Do you mean the total winnings is the sum of these rewards? Or do you mean the total winnings is the sum of these rewards minus $c_e$, in which case the player is charged $c_e$ to enter the game and then is charged $c_e$ again when he gets his reward? $\endgroup$ – Jihoon Kang Jul 31 '19 at 9:54
  • 1
    $\begingroup$ @JihoonKang $c_e$ is charged only once upon entering the game. I'll rephrase the question to make it clearer. $\endgroup$ – zegkljan Jul 31 '19 at 9:58
1
$\begingroup$

This is more of a discussion point than an answer. Let us assume $c_e < \sum_{i=1}^Nc_i$, otherwise this is a game nobody would play. It would also be illogical to terminate before the player has made the money $c_e$ back during the game (otherwise the player would just not play). Let $R_j=\sum_{i=1}^jc_i$, and let $1 \leq r \leq N$ be the minimum value for which $R_r=\sum_{i=1}^qc_i > c_e$. Let us consider what happens for the strategy "terminate after $k\geq r$ wins".

Notice that for this strategy there are only two outcomes, either the player wins $R_k-c_e$ with probability $p_k=\frac{N}{N+1}\times \cdots \frac{N-k+1}{N-k}=\frac{N-k+1}{N+1}$, or 'wins' $-c_e$ with probability $q_k=1-p_k=\frac{k}{N+1}$. So for each $k$ considered, we find ourselves a bernoulli distribution (on $\{C_k-c_e, -c_e\}$) with probability of success $p_k=\frac{N-k+1}{N+1}$.

At this point, we can look at the expected value $W_k$ for each of these strategies to get $$W_k = R_k\frac{N-k+1}{N+1} - c_e$$

if for any $k \geq r$ we get $W_k>0$, then our strategy is to find the largest $W_k$ and then terminate at $k$ and repeat. That is, if the player is allowed to play this game infinitely many times, then this would be a profitable strategy. This is kind of like playing the lottery, suppose the lottery gave a positive expected return (which it doesn't in reality), then playing the lottery infinitely often should result in a net profit over time, though playing it once is highly likely to result in a net loss.

So now suppose the player is only allowed to play the game once, then now it's a matter of a single bernoulli trial. Notice that for our strategy to terminate at $k$, $p_k$ is monotone decreasing in $k$, so we want to use the smallest posible value $k$. However, we also do not want to make any losses, so the smallest possible value of $k$ for which we still can make a profit is $r$, i.e we should terminate as soon as we win more money than we paid to play the game. Having said this, if $p_r$ is quite small (say $10\%$) then we win with only $10\%$ chance and it may not be worthwile for the player to play the game in the first place. One could argue that a large $R_r$ might make the game worthwile, but now this is a matter of personal opinion. Would you like to bet $£100$ say to win $£1001$ with $10\%$ chance? How about to win $£10001$ with $1\%$ chance?. Of course if we can play the game infinitely often, then these numbers are worthwile, but if we can only play once, most people would not play.

If say we are a casino trying to implement this game, we should ensure

  1. $W_k$ is never positive for any $k\geq r$
  2. $r$ is fairly large. i.e for anyone using the strategy to terminate after $r$ wins, the probability of them making money is $p_r=\frac{N-r+1}{N+1}$, where if $r$ is large then $p_r$ is small
$\endgroup$
  • $\begingroup$ Thanks for the answer, it is insightful. However, the conclusion regarding the situation where we are allowed to play only once seems strange. If $c_e$ is really small (e.g. significantly smaller than smallest $c_i$, or even zero) it would then mean that I should always terminate after the first round. Shouldn't the possible returns be considered as well than just maximizing the probability of a win? Yes, with this strategy I maximize the probability of positive return but I'm not maximizing the return itself. Or did I miss something? $\endgroup$ – zegkljan Jul 31 '19 at 10:53
  • $\begingroup$ You are exactly right, when I say use the smallest possible $k$ for which we should terminate only maximises the probability of winning but does not maximise the expected return. This is where the term "optimal" should be defined. If one wishes to "optimise" by increasing expected return, then the player should use the strategy as if they player is allowed to play infinitely often. However, calculating the expectation can often be misleading. If I offered you a chance to bet $£1000$ to win $£10000001$ with probability 0.0001, would you take it? (next comment) $\endgroup$ – Jihoon Kang Jul 31 '19 at 11:08
  • $\begingroup$ expected value says YES, but probabilitywise you should not take this best as you are VERY unlikely to win. Back to our game, if one wishes to "optimise "the probability of making a profit, then the strategy I suggested can be desirable. The problem with your question is the definition of "optimisation" and definition of "success" - what are you trying to optimise? My answer only explored some ideas, which I hope helped you with your ideas. $\endgroup$ – Jihoon Kang Jul 31 '19 at 11:09
  • 1
    $\begingroup$ I was asking for the expected return, that I get and seems ok. The only-once scenario is a bonus and I did not define the optimality criterion for it as I was not asking about it in the first place. Thanks for your insights, I get it now. $\endgroup$ – zegkljan Jul 31 '19 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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