Urns

infinity urns

Question by ? K-Dub ?: Any suggestions on this urn model problem?
An urn contains p balls labeled +1 and p balls labeled -1. The balls will be drawn out uniformly at random, without replacement, until the urn is empty. Before each ball is drawn, the player decides whether or not to place a bet on the next drawn ball.The payoff is the value of the ball drawn if the player bets. Otherwise, the ball is drawn, but nothing else happens. An optimal strategy is to place a bet if there are more +1 balls in the urn than -1 balls left in the urn. If there are an equal number of +1 and -1 balls, either option (pass/bet) is optimal, and if there are more -1 balls than +1 balls, the player will not bet. Here, assume the player will opt to pass on any “neutral” urn, e.g. the player won’t bet on the first ball.
The player has a “bank” B to work with. If at any time during the game the player’s bank is emptied, the player is ruined. It is my suspicion that if B is a fixed quantity, the probablility of ruin goes to 1 as p goes to infinity. How can I prove this? TIA
Ran out of room….

I’m looking at the probability of ruin under the stategy given.

I’m holding back some information, as I don’t want to lock anyone into a particular way of thinking.

Thanks in advance.
Yes, for this question I am forcing the player to use the outlined strategy (that is optimal if a player can go in and out of debt). B is a fixed number, say 100 – though I also believe that more generally, if B is a function of p, that if B = o(?p) then the ruin probability goes to one as p goes to infinity.
I want to show that a “poorer” player will be forced to alter his strategy from the optimal strategy, lessening his expected gain. The next question would be what kind of strategy should be used to maximize expected gain with the prospect of ruin (the original problem did not deal with ruin at all), and that is an even more complex problem that I want to tackle….. but first things first.
Thanks for the input. I really appreciate it.

A necessary, but not sufficient, condition for ruin is that at some stage, there are B+1 more +1 balls than -1 balls. If X(n) denotes the sum of the values of the balls left in the urn after n balls have been drawn, then X(0) = X(2p) = 0 and

X(n+1) = X(n) + 1 if a -1 ball is drawn; X(n) – 1 if a +1 ball is drawn.

So the necessary condition for ruin is that X(n) = B+1 for some n. But, for each time the urn value goes from value 1 to value 0, the player’s bank increases “permanently” by 1. (This is where gains are made in the original problem – without the bank.) So if a player starts with 2 dollars, if the urn passes from 1 to 0 in value 5 times, the urn will have to attain a value at least 8 (instead of 3) in order for the player to be ruined. So that cliff is not static, it can go.
I reckon I need to find a sufficient condition that is much simpler to work with. Any thoughts here?
John D, thanks for the info, it is appreciated. It gives me another place to look – I had not considered replacement. Ruin has to occur within 2p steps, though, and the gambler’s problem does not appear to deal with the time aspect. Even though p goes to infinity, it is still “finite.” I am still processing everything, though……

Best answer:

Answer by Phineas Bogg
I reckon we need more information about the player’s strategy, what he is trying to optimize, or whether he is ever forced to bet.

If the player is never forced to bet, then he will end up with B and a 0 probability of ruin. Even if he must bet once, he will end up with 2B is he bets on the last ball (which he will know the mark of), and have 0 probability of ruin. So if the player is trying to minimize his probability of ruin, he can certainly do it and end up with at least 2B, no matter how large p is.

I reckon an fascinating question is: what is the optimal expected result that a player can end up with, assuming that he can bet whenever he wants to and any amount that he want to? This amount grows slowly with p, but I am not sure what function of p it looks like as p goes to infinity.

Edit: do you mean that B is some fixed integer, which does not grow with p, and a bet must be 1 each time and the player is required to bet whenever the number of +1 and -1 balls is different? If so then I would agree with you that this does seem to have a probability of ruin which approaches 1 as p goes to infinity…

Edit2: Since we seem to be in agreement that the probability of ruin goes to infinity if you use the rule that you have to bet 1 every time your probability of winning is anything larger than 50%, I do not reckon that is optimal. We can certain analyze that strategy, but I do not believe it is right to assume that it is optimal and then say that deviating from it is suboptimal.

There is a straight forward, though not so pretty, way to get the strategy that maximizes the expected value. To get it, you have to fill in a p+1 by p+1 table with all of the possible numbers of +1 and -1 and then you can, starting from 0,0 and working up to p,p get the optimal expected values and bets. When p=1 then the table is rather simple, you bet 0 at 1,1 and all your money at 0,1 or 1,0.

EDIT3: I believe that if you start with (2p choose p) dollars you can guarentee that you will end up with exactly 4^p dollars, and bet an integral number of dollars (0 iff the number of +1 and -1 balls are equal) each turn. Note that 4^p divided by (2p choose p) is O(1/sqrt(n)). I will post more specifics when I have time.

What do you reckon? Answer below!