3
$\begingroup$

This question is a spin on the question Basic probability question but struggling (brain teaser with friend) but with some additional rules and considerations that make it more complex. The differences are that we can only make a single bet, and there is uncertainty about the composition of the urn.

We are looking for an optimal strategy for a person that is given the chance to place a bet in some game which has the following description and rules:

  • At the start we have an urn with $R$ red and $B$ blue balls and we know the total number of balls $R+B=N$, but we do not know $R$ and $B$ individually (except for a prior distribution explained in the last point).

  • Balls are drawn out of the urn one by one without replacement. Every turn, each remaining ball in the urn has equal probability to be drawn.

    We are allowed to see the colors of these balls that have been drawn from the urn, but we can not see the remaining balls in the urn (we have to guess this).

  • Each time that a ball is taken out of the urn, we are allowed to place a bet on the color of the next ball.

    If we bet then we look for the color of the next ball and if the bet is a correct guess then we win a prize.

    We can only make a bet once. After a bet, the game ends.

    If we do not bet, then the game continues by drawing the next ball from the urn.

  • The number of balls at the start with a specific color follow some prior distribution:

    $$P(R=r,B=b) \propto (r+1)^\alpha (b+1)^\beta \qquad \text{for all integer values $0<r<n$ and r+b = n}$$

    For simplicity one may consider $\alpha = \beta = 0$, but if a more general solution is possible that would be nice. (also if it makes the answer easier one may consider a uniform distribution for $0 \leq r \leq n$)

We are looking for a strategy that optimizes the expectation value of winning the prize. What is the strategy and what is the expectation value?

Improve this question
$\endgroup$
4
  • $\begingroup$ As a function of the number of drawn red and blue balls we can compute a posterior distribution for the number of the remaining red and blue balls and compute the expectation value when we choose to make a bet that turn. But that's only part of the answer. We need to know whether or not it is advantageous to continue or stop. $\endgroup$
    – Sextus Empiricus
    Jun 9 at 13:18
  • 1
    $\begingroup$ Curiously, if your prior had been ${n \choose r}/2^{n}$ then no matter when you bet and no matter what you had seen, the probability the next ball is red is always $\frac12$; if the prior had been ${n \choose r} p^r(1-p)^b$ then no matter when you bet and no matter what you had seen, the probability the next ball is red is always $p$ $\endgroup$
    – Henry
    Jun 10 at 1:56
  • $\begingroup$ @Henry After the answer by Joe Mansley, I started looking for such a prior. You prior makes sense, it is similar to drawing the n=r+b balls from another set with replacement, then drawing balls from the n balls, but that is just like drawing the balls directly with replacement. $\endgroup$
    – Sextus Empiricus
    Jun 10 at 4:51
  • $\begingroup$ I think Lewis Carroll may have had the binomial prior as one of his Pillow problems $\endgroup$
    – Henry
    Jun 10 at 9:23

2 Answers 2

Reset to default
4
$\begingroup$

Betting on the last ball is an optimal strategy, regardless of what the prior is.

Here's how I know: Imagine that after seeing 8 balls, you decide to bet that the 9th ball is red. This is equivalent to drawing the remaining balls and ignoring their color, and then betting that the Nth ball is red.

Improve this answer
$\endgroup$
4
$\begingroup$

Below is a recipe to compute the expectation value for winning the prize

1] As a function of the number of drawn red and blue balls (let's call them $x_r$ and $x_b$) we can compute a posterior distribution for the number of the remaining red and blue balls and compute the probability that the next ball is red or blue. Let's call these probabilities $P_r(x_r,x_b)$ and $P_b(x_r,x_b)$

2] Assume that there is an optimal solution such that given $x_r$ and $x_b$ the expectation of winning the prize is $W(x_r,x_b)$. Then we can express these in terms of an iterative scheme

$$W(x_r,x_b) = \max \begin{bmatrix} P_r(x_r,x_b)W(x_r+1,x_b) + P_b(x_r,x_b)W(x_r,x_b+1) \\ P_r(x_r,x_b) \\ P_b(x_r,x_b) \end{bmatrix}$$

That is, if we choose to bet then the expectation value is the maximum of $P_r(x_r,x_b)$ and $P_b(x_r,x_b)$ (we choose to bet for whichever of the two colors is bigger. If we continue, then the expectation value is $P_r(x_r,x_b)W(x_r+1,x_b) + P_b(x_r,x_b)W(x_r,x_b+1) $. If the latter is bigger than the former, then the best strategy is to continue.

Here is a computation:

n = 10
alpha = 0
beta = 0

prior = function(r,b,alpha = 0, beta = 0, normconstant = 1) {
  p = r^alpha*b^beta*normconstant
  p[p==Inf] = 0
  return(p)
}

posterior = function(r,b,n,alpha = 0, beta = 0) {
  reds = r:n                   ### possible values for the number of red balls
  likelihood = c(rep(0,r),dhyper(r,reds,n-reds,r+b)) 
  
  reds = 0:n
  prior = prior(reds,n-reds,alpha = alpha, beta = beta)
  
  posterior = prior*likelihood
  posterior = posterior/sum(posterior)   #normalize
  return(posterior)
}

Pr = function(r,b,n, alpha = 0, beta = 0) {
    ### compute posterior
    pr = posterior(r,b,n,alpha = alpha, beta = beta)
    
    reds = 0:n
    remaining_reds = reds-r
    remaining_blue = n-reds-b
    
    ### integrate posterior probability of a red    
    red_frac = remaining_reds/(remaining_reds+remaining_blue)
    Pr = sum(red_frac*pr)
    return(Pr)
}
  
E = matrix(rep(0,(n+2)*(n+2)),n+2)
stopping = matrix(rep(0,(n+2)*(n+2)),n+2)


### compute the iterative scheme
for (n_drawn in (n-1):0) {
  for (k_red in 0:n_drawn) {
    k_blue = n_drawn-k_red
    
    prob_red = Pr(k_red,k_blue,n,alpha,beta)
    prob_blue = 1-prob_red
    E_cont = prob_red*E[k_red+1+1,k_blue+1] + prob_blue*E[k_red+1,k_blue+1+1]
    
    E[k_red+1,k_blue+1] = max(prob_red,prob_blue,E_cont)
    
    if (E_cont < max(prob_red,prob_blue)) {
      stopping[k_red+1,k_blue+1] == 1
    }
  }
}


E[E == 0] = NA
round(E,3)
stopping

and it looks like

> round(E,3)
       [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10] [,11] [,12]
 [1,] 0.727 0.727 0.765 0.803 0.834 0.857 0.875 0.889 0.900 0.909    NA    NA
 [2,] 0.727 0.652 0.652 0.680 0.716 0.750 0.778 0.800 0.818    NA    NA    NA
 [3,] 0.765 0.652 0.608 0.608 0.633 0.667 0.700 0.727    NA    NA    NA    NA
 [4,] 0.803 0.680 0.608 0.576 0.576 0.600 0.636    NA    NA    NA    NA    NA
 [5,] 0.834 0.716 0.633 0.576 0.545 0.545    NA    NA    NA    NA    NA    NA
 [6,] 0.857 0.750 0.667 0.600 0.545    NA    NA    NA    NA    NA    NA    NA
 [7,] 0.875 0.778 0.700 0.636    NA    NA    NA    NA    NA    NA    NA    NA
 [8,] 0.889 0.800 0.727    NA    NA    NA    NA    NA    NA    NA    NA    NA
 [9,] 0.900 0.818    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA
[10,] 0.909    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA
[11,]    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA
[12,]    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA    NA
> stopping
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
 [1,]    0    0    0    0    0    0    0    0    0     0     0     0
 [2,]    0    0    0    0    0    0    0    0    0     0     0     0
 [3,]    0    0    0    0    0    0    0    0    0     0     0     0
 [4,]    0    0    0    0    0    0    0    0    0     0     0     0
 [5,]    0    0    0    0    0    0    0    0    0     0     0     0
 [6,]    0    0    0    0    0    0    0    0    0     0     0     0
 [7,]    0    0    0    0    0    0    0    0    0     0     0     0
 [8,]    0    0    0    0    0    0    0    0    0     0     0     0
 [9,]    0    0    0    0    0    0    0    0    0     0     0     0
[10,]    0    0    0    0    0    0    0    0    0     0     0     0
[11,]    0    0    0    0    0    0    0    0    0     0     0     0
[12,]    0    0    0    0    0    0    0    0    0     0     0     0

which verifies Joe Mansley's answer, that it is optimal to continue until only a single ball is left.

Improve this answer
$\endgroup$

Your Answer

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

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