Author |
Topic: Clarification on card-calling (Read 2725 times) |
|
Chronos
Full Member
 
Gender: 
Posts: 288
|
 |
Clarification on card-calling
« on: Dec 10th, 2002, 3:09pm » |
 Quote  Modify
|
I'm a little unclear about one point in the riddle Calling a Card's Color. What happens if the entire deck plays out, and you still haven't guessed? I can think of two plausible interpretations: First, that might mean that it's a tie, and you play again. In this case, the optimal strategy is to wait until 51 cards have been played out, and then only guess if all 26 of the black cards have been played (equivalently, he could guess as soon as all 26 blacks are taken out of circulation, but this offers no advantage or disadvantage over waiting until the end). The second interpretation I can come up with is that if the deck runs out without a guess, the player loses. In this case, one possible winning method (i.e., probability greater than 50% of winning) is to wait until all but one of the red cards have been drawn, and then make your guess. There's a 50% chance that this will occur at 51 cards drawn (only one card left in the deck), in which case victory is assured. And even if it happens before then, there's still a nonzero chance that you'll win, so the probability favors the player.
I don't know, though, whether this is optimum. One might also, for instance, decide to call if at any time the number of red cards remaining is greater than the number of black cards remaining, and still get better than 50% odds. I haven't yet calculated which of these methods is better, not to mention any other potential methods.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Clarification on card-calling
« Reply #1 on: Dec 11th, 2002, 12:18am » |
Quote Modify
|
I think the trick is to find a number x > 0, and guess red when there are x more black cards than red laid out.. And guess the 52nd card if you passed on the first 51..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Clarification on card-calling
« Reply #2 on: Dec 13th, 2002, 2:14pm » |
Quote Modify
|
If that's your method, towr, then you probably shouldn't make x a constant, but rather depend on the number of cards left. "Red ahead by three cards", say, means something completely different at the beginning and the end.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Clarification on card-calling
« Reply #3 on: Dec 15th, 2002, 2:14am » |
Quote Modify
|
on Dec 10th, 2002, 3:09pm, Chronos wrote:| I'm a little unclear about one point in the riddle Calling a Card's Color.The second interpretation I can come up with is that if the deck runs out without a guess, the player loses. In this case, one possible winning method (i.e., probability greater than 50% of winning) is to wait until all but one of the red cards have been drawn, and then make your guess. There's a 50% chance that this will occur at 51 cards drawn (only one card left in the deck), in which case victory is assured. And even if it happens before then, there's still a nonzero chance that you'll win, so the probability favors the player. |
|
If you don't guess, you lose. I will make that clear in the next site update.
This is a nice puzzle, so I'll let you guys think about it some more for a while. If you're still stuck, I can give you the same hint Chronos gave someone else in this forum a little while ago.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Clarification on card-calling
« Reply #4 on: Dec 15th, 2002, 8:12am » |
Quote Modify
|
on Dec 13th, 2002, 2:14pm, Chronos wrote:| If that's your method, towr, then you probably shouldn't make x a constant, but rather depend on the number of cards left. "Red ahead by three cards", say, means something completely different at the beginning and the end. |
|
You're probably right, but it's easier to model.. Else you have need 26*25 different cases for which to decide wheter to guess now or guess later.
Though I guess if you use a computer it shouldn't be too hard to find an optimum..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Clarification on card-calling
« Reply #5 on: Dec 15th, 2002, 2:32pm » |
Quote Modify
|
I think the player can expect to win half the time. The reasoning Chronos used to demonstrate a winning strategy is flawed. True that red will be the last card 50% of the time, but if using the strategy of waiting until exactly 1 red left, there could be from 0 to 26 black cards left when you first get 1 red remaining.
If there are N cards left and r of them are red, let Er,N be the expected probability of winning when using the best strategy. When N is 1, E0,1=0 (i.e. one black card left) and E1,1=1 (i.e. one red card left). Thus for N=1, Er,N=r/N. Will use induction to show this is true for all N.
When N+1 cards left with r of them red, the probability of winning if you choose this turn as the one to bet on is r/(N+1). If you decide to pass and bet later, the expectation is probability next card is red times expectation of r-1 red and N cards plus probability next card is black times expectation of r red cards out of N or in equation form:
Er-1,N*r/(N+1)+Er,N*(N+1-r)/(N+1)
Plugging in Er,N=r/N, this simplifies to r/(N+1). So it is the same whether you bet on this card or pass and Er,N=r/N not just for N=1, but also N>1.
At the beginning of the game, r=26 and N=52, so E26,52=0.5.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Clarification on card-calling
« Reply #6 on: Dec 15th, 2002, 6:16pm » |
Quote Modify
|
swf, I think that you're trying to do a two-dimensional induction there, but only applying the inductive step for one dimension. In your formula for Er,N+1, I agree that you can plug in our inductive-hypothesis value for Er,N, but that still leaves us without a value for Er-1,N, so we can't evaluate the whole expression.
Yes, my strategy will leave anywhere from 0 to 26 black cards in the deck when I guess, and I agree that if there are 26 black cards left, my situation looks pretty bleak. But that doesn't happen very often: The probability of getting 25 reds in a row before any blacks is only about 5*10-14, by my calculations. In fact, the most likely number of black cards remaining is zero, with a probability of 0.5 . Since I always win when the last card in the deck is red, and sometimes win even when it isn't, I can't see how my expectation could be 50%.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Clarification on card-calling
« Reply #7 on: Dec 16th, 2002, 5:24pm » |
Quote Modify
|
Never mind, I see my flaw now. Even if the last card is red, my method won't necessarily make it all the way to the last card. If the last three cards are 50:r, 51:b, 52:r, for instance, then my method would have me stop after the 50th card.
On further reflection, I think that SWF is right. Consider just two alternatives: Either I decide to guess now, or I decide now to guess after the next card. If I guess now, with N cards left in the deck of which r are red, then my expectation is r/N. If I postpone my guess exactly one round, then my expectation is r/N * (r-1)/(N-1) + (1 - r/N) * r/(N-1). Which, surprise surprise, reduces to exactly r/N (provided N != 1, which is a boundary case anyway). So at any given point in the game, my expectation for guessing now is the same as my expectation for guessing next turn. We can induce this without any problem, and find that nothing we can do matters at all.
So how the heck did SWF manage to use Influence on me  ?
|
|
IP Logged |
|
|
|
wenbiao
Guest
|
|
(another problem, how to bet?!)
« Reply #8 on: Apr 10th, 2003, 7:15pm » |
Quote Modify
 Remove
|
There is a stack of 52 cards with 26 of them red and 26 of them black. Draw cards sequentially. If a red one you get 1 point. If a black one you lose 1 point. What is the optimal betting strategy so as to maximize the final score. In other words, when should you stop given the previous sequence?
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Clarification on card-calling
« Reply #9 on: Apr 13th, 2003, 2:23pm » |
Quote Modify
|
Ah, in that case, wenbiao, we do have a positive expectation. At worst, if we're ever down, then we can just wait until the end of the deck, when we'll eventually get back to 0. And at best, we can quit at any time that we're ahead.
I think that the optimum strategy here is to quit as soon as you're ahead, if that ever happens, or if not, to quit at the end when we're back to 0 points. If you're ahead by any amount, then the next card is more likely to cost you a point than it is to gain you a point, so your expectation on the next card is negative.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Clarification on card-calling
« Reply #10 on: Apr 6th, 2005, 11:23pm » |
Quote Modify
|
wenbaio posted an interesting question here. Chronos' guess that you should quit when you get ahead be one is incorrect - although you may have a better chance of decreasing than increasing after the next draw, you still have positive expectation even if you drop to zero. A quick calculation shows that, with three black cards and two red cards left, the expected return is 1.2 using the optimal strategy. So it's still open...
An easier question - if there are x black cards and y red cards left (so your score is x - y), and you keep drawing until only black cards are left, what is your expected score?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Clarification on card-calling
« Reply #11 on: Apr 8th, 2005, 5:17am » |
Quote Modify
|
on Apr 6th, 2005, 11:23pm, Deedlit wrote:| An easier question - if there are x black cards and y red cards left (so your score is x - y), and you keep drawing until only black cards are left, what is your expected score? |
|
Using induction, I get: y(x-y)/(y+1).
P.S. Please ignore this: it's simply wrong!
|
| « Last Edit: Apr 8th, 2005, 8:25am by Barukh » |
IP Logged |
|
|
|
markr
Junior Member
Gender:
Posts: 90
|
|
Re: Clarification on card-calling
« Reply #12 on: Apr 8th, 2005, 9:12pm » |
Quote Modify
|
I get:
(x-y) + 1/C(y+x,x) * SUM[i=0 to x, C(y+i-1,i) * (y-i)]
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Clarification on card-calling
« Reply #13 on: Apr 9th, 2005, 2:51pm » |
Quote Modify
|
This looks right, but the expression I have is a lot simpler than that!
For wenbaio's original question, the exact value may be an intractible problem, but I can say the following: if f(n) is how high a score you need to be willing to quit with n cards left, then it's not too hard to show that f(n) = theta(sqrt(n)). Choose k to be large, and choose n so that n/k is large; then the first [n/k] draws are very close to a simple random walk. Then for any e, there is a d such that the probability that the score surpasses d sqrt(n/k) is greater than 1-e. On the other hand, for any e there is a d such that the probability that the score surpasses d sqrt(n/k) is less than e. So f(n) is bounded above and below with respect to sqrt(n).
|
|
IP Logged |
|
|
|
markr
Junior Member
Gender:
Posts: 90
|
|
Re: Clarification on card-calling
« Reply #14 on: Apr 9th, 2005, 4:59pm » |
Quote Modify
|
x/(y+1) is a lot simpler!
|
| « Last Edit: Apr 9th, 2005, 9:22pm by markr » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Clarification on card-calling
« Reply #15 on: Apr 9th, 2005, 10:57pm » |
Quote Modify
|
Indeed; do you have a simple proof?
|
|
IP Logged |
|
|
|
markr
Junior Member
Gender:
Posts: 90
|
|
Re: Clarification on card-calling
« Reply #16 on: Apr 10th, 2005, 10:07pm » |
Quote Modify
|
Unfortunately, no.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Clarification on card-calling
« Reply #17 on: Apr 10th, 2005, 10:23pm » |
Quote Modify
|
Think about what the question is asking; is there an "obvious" guess at the answer?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Clarification on card-calling
« Reply #18 on: Apr 12th, 2005, 1:48am » |
Quote Modify
|
Don’t know if simple enough, but here’s a proof.
Let E(x,y) be sought score. It is clear that E(0,y) = 0, E(x,0) = x. Also, the following recurrence is straightforward:
(x+y) E(x,y) = x E(x-1,y) + y E(x,y-1) (1)
Now, consider another function F(x,y) = (y+1)E(x,y). For x=1, the above relation simply becomes F(1,y) = F(1,y-1), and because F(1,0) = 1, it follows F(1,y) =1.
Now the induction step: assuming F(x-1,y) = x-1, let’s show that F(x,y) = x. Multiplying both sides of (1) by (y+1), we get:
(x+y) F(x,y) = x F(x-1,y) + (y+1) F(x,y-1),
which after rearranging and using induction hypothesis becomes:
(x+y) (F(x,y) – F(x,y-1)) = (x-1) (x - F(x,y-1)).
Again, F(x,0) = x, therefore F(x,y) = F(x,y-1) = x for any y.
|
| « Last Edit: Apr 12th, 2005, 1:49am by Barukh » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Clarification on card-calling
« Reply #19 on: Apr 12th, 2005, 8:13am » |
Quote Modify
|
That works, but I was looking for a more revealing proof. Generally speaking, just about any proof without induction beats just about any proof with induction!
Note that, after the last red card, you have a string of black cards. What would be a naive guess as to the number of black cards?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Clarification on card-calling
« Reply #20 on: Apr 25th, 2005, 6:09pm » |
Quote Modify
|
Anyway, here's what I was looking for:
Basically, you're looking for the length of the final run of black cards. The permutations of x black cards and y red cards can be mapped bijectively to the set of (y+1)-tuples
(x0,...,xy+1)
under the constraint [sum] xi = x, by setting xi to the length of the ith run of black cards. (xi can be zero, if there are two consecutive red cards) Clearly the xi are symmetric - a function switching the values of xi and xj will be a bijection - so each place has the same average value, which must be x/(y+1).
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Clarification on card-calling
« Reply #21 on: Apr 26th, 2005, 9:39am » |
Quote Modify
|
Deedlit, how would you say in such a case? That's neat! 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print