2
$\begingroup$

There are 4 red balls and 3 blue balls in an urn. Picking red balls gives you 1 dollar and picking blue balls means you have to pay 1 dollar. You can stop picking balls at any point.

What is the expected value of this game, given that you play rationally?

This is an interesting question. I've realized that the lower bound on the EV is 1 dollar, because even if you pick all the blue balls, you can just pick all the red balls to get a net of 1 dollar. However, I don't know how to do the case work on the other possible outcomes of drawing balls, and it seem overly complicated.

$\endgroup$
12
  • $\begingroup$ I assume that you meant to say that the player can stop whenever they like? Assuming that this is the case, problems like these can best be done by backwards induction. Create a state $(r,b)$ for $r$ red and $b$ blue remaining, with $0≤r≤4$ and $0≤b≤3$. We know the value of $(0,0)$ is $1$ so you can compute the value of $(1,0)$ and $(0,1)$. Continue from there. $\endgroup$
    – lulu
    Jul 1, 2020 at 21:51
  • $\begingroup$ Yes, sorry, I did mean to say that. Okay, that seems interesting. The value of (0,0) would be 0 though, right, because you have 0 balls to gain money from and 0 balls to lose money from, so nothing happens? $\endgroup$ Jul 2, 2020 at 0:34
  • $\begingroup$ No. In state $(0,0)$ there are no balls left to choose. Hence you have chosen all the balls, in which case you are up $1$. So the intrinsic value of that state is $1$. There is no option value in that state (as the game has ended) so the final value is $1$. $\endgroup$
    – lulu
    Jul 2, 2020 at 0:44
  • $\begingroup$ There is a well known version of this problem played with an ordinary deck of cards. You draw from the deck without replacement and get a dollar for every red card and lose a dollar for every black card. The expected value of the game is obviously positive (since you might get a profit and can always play to $0$). Computing it, however, is generally done by the same backwards induction scheme I mentioned. $\endgroup$
    – lulu
    Jul 2, 2020 at 0:48
  • $\begingroup$ To clarify: in my notation, $(r,b)$ denotes the number of each type $\textit {remaining}$. Thus, the state $(0,0)$ for your game means that all $4$ red and all $3$ blue have been chosen already. You can use different notation if you prefer. I like my choice because you can read off the transition probabilities. $\endgroup$
    – lulu
    Jul 2, 2020 at 0:49

1 Answer 1

2
$\begingroup$

This is a variant of the somewhat well known red and black card problem. The general question is: if you start with $R$ red balls and $B$ blues and play according to the rules specified above, what is your expected return?

The problem is difficult because of the option. At any stage you have to compare the value of quitting where you stand to the value of drawing one more ball. Such option problems are traditionally handled by backwards induction. The thinking is that you have an enormous amount of information about what to do at the very end and you can start there and work back to the start.

Toward that end, we define all the possible states of the game via in terms of the remaining balls. Thus the state $(r,b)$ means there are $r$ red balls and $b$ blue balls left to draw from. Being in that state means that you have previously drawn $R-r$ red balls and $B-b$ blue ones so the intrinsic value of that state (the value you get if you quit then and there) is given by $$I(r,b)=R-r-(B-b)=(R-B)+(b-r)$$

Of course the states also have option value. Let's denote that by $O(r,b)$. We then let $V(r,b)$ denote the true Value of the state and we have $$V(r,b)=\max \left(I(r,b),\,O(r,b)\right)$$

That definition reflects the "optimal play": At any point you do whatever it takes to maximize your expected value.

Now, we have to compute $O(r,b)$ If you are in the state $(r,b)$ then you can move to either $(r-1,b)$ or $(r,b-1)$ (at least if both $r,b≥1$). The probability of moving to $(r-1,b)$ is $\frac r{r+b}$ and the probability of moving to $(r,b-1)$ is $\frac b{r+b}$. It follows that $$\boxed {O(r,b)=\frac r{r+b}\times V(r-1,b)+\frac b{r+b}\times V(r,b-1)}$$

That is the key recursion.

In your case, for example, we have $R=4,B=3$ so $V(0,0)=1$. We can then use the recursion to compute $V(1,0)$, say. We have $I(1,0)=0$ and $O(1,0)=1\times 1=1$. Thus in this case your best move is to keep on drawing and we get $$V(1,0)=1$$

Similarly $I(0,1)=2$ and $O(0,1)=1\times 1=1$ so this time your best move is to quit and take the $2$ you currently hold. Thus $$V(0,1)=2$$

We could then compute $V(2,0),V(1,1),V(0,2)$ and so on.

The numbers involved in your problem are so small that you can do it with pencil and paper. It's a bit tedious, and somewhat error prone, but it is not difficult. Of course the method lends itself to automation and for larger numbers (like the red and black card problem) you need to do it on a machine.

I did your problem quickly and I got $$V(4,3)=\frac {58}{35}\approx 1.657$$

which seems sensible to me but, as I mentioned, the computation is a bit error prone so I suggest checking it carefully.

$\endgroup$
3
  • $\begingroup$ I appreciate all of your help. What an incredible explanation. Thanks! :) $\endgroup$ Jul 2, 2020 at 17:27
  • $\begingroup$ Is there a reason why in the solution that you linked, they add 1+ and -1+ in the recursion, but here we don't? $\endgroup$ Jul 2, 2020 at 18:10
  • $\begingroup$ Yes. Their approach is slightly different than mine...they compute the value of being dropped into that state, whereas my value function retains the profit (or loss) you achieved in getting to that state. The $\pm 1$ terms in their recursion explain how that "past" value is accounted for. I prefer my method, because it keeps the recursion a bit cleaner, but it's really equivalent. $\endgroup$
    – lulu
    Jul 2, 2020 at 18:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .