Re: [math-fun] playing card color guessing game
Although I believe this: ----- Hmm, strategy seems clear: guess the majority color remaining, if any ----- , I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times? Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant. On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang. You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end. Instead, what if the winner is defined to be *the one who was *leading* more*. Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other. If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties? Now: Onward, to the third-order effects. —Dan
Neat question! Google search for the exact answer (3724430600965475/123979633237026, as Tom said) turns up a hit in Russian; translation at https://translate.google.com/translate?hl=en&sl=ru&u=https://habr.com/users/... Ah, and Google search for just the numerator yields a hit on https://www.jstor.org/stable/2687606. Registering for a free JSTOR account, that URL shows me that this was Problem #630, "Guessing Card Colors", appearing with solution in The College Mathematics Journal Vol. 30, No. 3 (May, 1999), pp. 234-235. The problem was posed my Michael Andreoli, Miami-Dade Community College (North), Miami, FL, and the published solution was by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA. Andreoli's formulation of the problem there presupposes that you always guess the more-likely color (and guess randomly when tied), which as Cris says is optimal. Steelman proves that for m red cards and n black cards with m >= n, the expected value is E(m,n) = m + sum{k=0..n-1} binomial(m+n,k)/binomial(m+n,n) The proof is by induction on m+n. When m=n, this simplifies to E(n,n) = n - 1/2 + 2^(2n-1)/binomial(2n,n) Ah: And there's an editor's note that one of the solvers (Michael Vowe of Therwil, Switzerland) pointed out that this is a special case of Problem #4661 from the American Math Monthly, vol 63 (1956), pp. 51-53. But I haven't tried to track down the AMM article to see what the generalization is -- maybe to drawing marbles out of an urn with more than 2 colors? --Michael On Wed, Dec 26, 2018 at 6:10 PM Dan Asimov <dasimov@earthlink.net> wrote:
Although I believe this:
----- Hmm, strategy seems clear: guess the majority color remaining, if any -----
, I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times?
Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant.
On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang.
You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end.
Instead, what if the winner is defined to be *the one who was *leading* more*.
Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other.
If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties?
Now: Onward, to the third-order effects.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Heh, I should have done the algebra! Nice find. Knuth's Concrete Math taught me a lot of neat tricks for working with binomials; I should have taken this opportunity to try them out. That solution (for n=m) is remarkably concise. -tom On Wed, Dec 26, 2018 at 9:01 PM Michael Kleber <michael.kleber@gmail.com> wrote:
Neat question!
Google search for the exact answer (3724430600965475/123979633237026, as Tom said) turns up a hit in Russian; translation at
https://translate.google.com/translate?hl=en&sl=ru&u=https://habr.com/users/...
Ah, and Google search for just the numerator yields a hit on https://www.jstor.org/stable/2687606. Registering for a free JSTOR account, that URL shows me that this was Problem #630, "Guessing Card Colors", appearing with solution in The College Mathematics Journal Vol. 30, No. 3 (May, 1999), pp. 234-235. The problem was posed my Michael Andreoli, Miami-Dade Community College (North), Miami, FL, and the published solution was by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA. Andreoli's formulation of the problem there presupposes that you always guess the more-likely color (and guess randomly when tied), which as Cris says is optimal.
Steelman proves that for m red cards and n black cards with m >= n, the expected value is
E(m,n) = m + sum{k=0..n-1} binomial(m+n,k)/binomial(m+n,n)
The proof is by induction on m+n. When m=n, this simplifies to
E(n,n) = n - 1/2 + 2^(2n-1)/binomial(2n,n)
Ah: And there's an editor's note that one of the solvers (Michael Vowe of Therwil, Switzerland) pointed out that this is a special case of Problem #4661 from the American Math Monthly, vol 63 (1956), pp. 51-53. But I haven't tried to track down the AMM article to see what the generalization is -- maybe to drawing marbles out of an urn with more than 2 colors?
--Michael
On Wed, Dec 26, 2018 at 6:10 PM Dan Asimov <dasimov@earthlink.net> wrote:
Although I believe this:
----- Hmm, strategy seems clear: guess the majority color remaining, if any -----
, I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times?
Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant.
On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang.
You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end.
Instead, what if the winner is defined to be *the one who was *leading* more*.
Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other.
If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties?
Now: Onward, to the third-order effects.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
This is fairly straightforward when considered in terms of a random walk where the position S_k of the random walk at stage k represents the difference between the numbers of red and black card remaining. As previously discussed an optimal strategy always chooses red when S_k > 0, black when S_k < 0 and randomly chooses when S_k = 0. By mirroring any path, we have that S_k is always nonnegative. When S_k > 0 we guess red and we will be correct and win a dollar whenever the random walk takes a downward step. Starting from S_0 = 0 and ending at S_{2n} = 0, there must be n downward steps so we win n dollars. In addition, whenever S_k = 0, we win a dollar with probability 1/2. So our total winnings are n + (1/2) * expected number of times S_k > 0: 1 <= k <= 2n. By linearity of expectations, expected number of times S_k = 0: 1 <= k <= 2n is simply sum_{k=1}^{2n} P{S_k = 0 | S_{2n} = 0} = sum_{k=1}^n P{S_{2k} = 0 | S_{2n} = 0}. Now P{S_{2k} = 0} = binomial{2k, k}/2^{2k} so: P{S_{2k} = 0 | S_{2n} = 0} = P{S_{2n} = 0 | S_{2k} = 0}P{S_{2k} = 0}/P{S_{2n} = 0} = binomial{2(n - k), n - k}binomial{2k, k}/binomial{2n, n}. A standard identity for binomial coefficients tells us that sum_{k=0}^n binomial{2(n - k), n - k}binomial{2k, k} = 2^{2n} so our expected winnings are given by n + (1/2)(2^{2n}/binomial{2n, n} - 1) = n - 1/2 + 2^{2n - 1}/binomial{2n, n} which matches with the expression Michael quoted above. A little bit of extra work gives the more general result. --Richard On Wednesday, December 26, 2018, 9:07:08 PM PST, Tomas Rokicki <rokicki@gmail.com> wrote: Heh, I should have done the algebra! Nice find. Knuth's Concrete Math taught me a lot of neat tricks for working with binomials; I should have taken this opportunity to try them out. That solution (for n=m) is remarkably concise. -tom On Wed, Dec 26, 2018 at 9:01 PM Michael Kleber <michael.kleber@gmail.com> wrote:
Neat question!
Google search for the exact answer (3724430600965475/123979633237026, as Tom said) turns up a hit in Russian; translation at
https://translate.google.com/translate?hl=en&sl=ru&u=https://habr.com/users/...
Ah, and Google search for just the numerator yields a hit on https://www.jstor.org/stable/2687606. Registering for a free JSTOR account, that URL shows me that this was Problem #630, "Guessing Card Colors", appearing with solution in The College Mathematics Journal Vol. 30, No. 3 (May, 1999), pp. 234-235. The problem was posed my Michael Andreoli, Miami-Dade Community College (North), Miami, FL, and the published solution was by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA. Andreoli's formulation of the problem there presupposes that you always guess the more-likely color (and guess randomly when tied), which as Cris says is optimal.
Steelman proves that for m red cards and n black cards with m >= n, the expected value is
E(m,n) = m + sum{k=0..n-1} binomial(m+n,k)/binomial(m+n,n)
The proof is by induction on m+n. When m=n, this simplifies to
E(n,n) = n - 1/2 + 2^(2n-1)/binomial(2n,n)
Ah: And there's an editor's note that one of the solvers (Michael Vowe of Therwil, Switzerland) pointed out that this is a special case of Problem #4661 from the American Math Monthly, vol 63 (1956), pp. 51-53. But I haven't tried to track down the AMM article to see what the generalization is -- maybe to drawing marbles out of an urn with more than 2 colors?
--Michael
On Wed, Dec 26, 2018 at 6:10 PM Dan Asimov <dasimov@earthlink.net> wrote:
Although I believe this:
----- Hmm, strategy seems clear: guess the majority color remaining, if any -----
, I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times?
Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant.
On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang.
You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end.
Instead, what if the winner is defined to be *the one who was *leading* more*.
Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other.
If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties?
Now: Onward, to the third-order effects.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The numerators and denominators of E(n,n) are now A322755, A322756. (The latter is twice A001790.) On Thu, Dec 27, 2018 at 1:30 PM Richard Chatwin via math-fun < math-fun@mailman.xmission.com> wrote:
This is fairly straightforward when considered in terms of a random walk where the position S_k of the random walk at stage k represents the difference between the numbers of red and black card remaining. As previously discussed an optimal strategy always chooses red when S_k > 0, black when S_k < 0 and randomly chooses when S_k = 0. By mirroring any path, we have that S_k is always nonnegative. When S_k > 0 we guess red and we will be correct and win a dollar whenever the random walk takes a downward step.
Starting from S_0 = 0 and ending at S_{2n} = 0, there must be n downward steps so we win n dollars. In addition, whenever S_k = 0, we win a dollar with probability 1/2. So our total winnings are n + (1/2) * expected number of times S_k > 0: 1 <= k <= 2n. By linearity of expectations, expected number of times S_k = 0: 1 <= k <= 2n is simply sum_{k=1}^{2n} P{S_k = 0 | S_{2n} = 0} = sum_{k=1}^n P{S_{2k} = 0 | S_{2n} = 0}. Now P{S_{2k} = 0} = binomial{2k, k}/2^{2k} so: P{S_{2k} = 0 | S_{2n} = 0} = P{S_{2n} = 0 | S_{2k} = 0}P{S_{2k} = 0}/P{S_{2n} = 0} = binomial{2(n - k), n - k}binomial{2k, k}/binomial{2n, n}. A standard identity for binomial coefficients tells us that sum_{k=0}^n binomial{2(n - k), n - k}binomial{2k, k} = 2^{2n} so our expected winnings are given by n + (1/2)(2^{2n}/binomial{2n, n} - 1) = n - 1/2 + 2^{2n - 1}/binomial{2n, n} which matches with the expression Michael quoted above. A little bit of extra work gives the more general result. --Richard
On Wednesday, December 26, 2018, 9:07:08 PM PST, Tomas Rokicki < rokicki@gmail.com> wrote:
Heh, I should have done the algebra! Nice find.
Knuth's Concrete Math taught me a lot of neat tricks for working with binomials; I should have taken this opportunity to try them out.
That solution (for n=m) is remarkably concise.
-tom
On Wed, Dec 26, 2018 at 9:01 PM Michael Kleber <michael.kleber@gmail.com> wrote:
Neat question!
Google search for the exact answer (3724430600965475/123979633237026, as Tom said) turns up a hit in Russian; translation at
https://translate.google.com/translate?hl=en&sl=ru&u=https://habr.com/users/...
Ah, and Google search for just the numerator yields a hit on https://www.jstor.org/stable/2687606. Registering for a free JSTOR account, that URL shows me that this was Problem #630, "Guessing Card Colors", appearing with solution in The College Mathematics Journal Vol. 30, No. 3 (May, 1999), pp. 234-235. The problem was posed my Michael Andreoli, Miami-Dade Community College (North), Miami, FL, and the published solution was by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA. Andreoli's formulation of the problem there presupposes that you always guess the more-likely color (and guess
randomly
when tied), which as Cris says is optimal.
Steelman proves that for m red cards and n black cards with m >= n, the expected value is
E(m,n) = m + sum{k=0..n-1} binomial(m+n,k)/binomial(m+n,n)
The proof is by induction on m+n. When m=n, this simplifies to
E(n,n) = n - 1/2 + 2^(2n-1)/binomial(2n,n)
Ah: And there's an editor's note that one of the solvers (Michael Vowe of Therwil, Switzerland) pointed out that this is a special case of Problem #4661 from the American Math Monthly, vol 63 (1956), pp. 51-53. But I haven't tried to track down the AMM article to see what the generalization is -- maybe to drawing marbles out of an urn with more than 2 colors?
--Michael
On Wed, Dec 26, 2018 at 6:10 PM Dan Asimov <dasimov@earthlink.net> wrote:
Although I believe this:
----- Hmm, strategy seems clear: guess the majority color remaining, if any -----
, I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times?
Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant.
On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang.
You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end.
Instead, what if the winner is defined to be *the one who was *leading* more*.
Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other.
If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties?
Now: Onward, to the third-order effects.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Neil: those sequences are about a 2n-card deck, not an n-card deck. --Michael On Thu, Dec 27, 2018 at 12:02 PM Neil Sloane <njasloane@gmail.com> wrote:
The numerators and denominators of E(n,n) are now A322755, A322756. (The latter is twice A001790.)
On Thu, Dec 27, 2018 at 1:30 PM Richard Chatwin via math-fun < math-fun@mailman.xmission.com> wrote:
This is fairly straightforward when considered in terms of a random walk where the position S_k of the random walk at stage k represents the difference between the numbers of red and black card remaining. As previously discussed an optimal strategy always chooses red when S_k > 0, black when S_k < 0 and randomly chooses when S_k = 0. By mirroring any path, we have that S_k is always nonnegative. When S_k > 0 we guess red and we will be correct and win a dollar whenever the random walk takes a downward step.
Starting from S_0 = 0 and ending at S_{2n} = 0, there must be n downward steps so we win n dollars. In addition, whenever S_k = 0, we win a dollar with probability 1/2. So our total winnings are n + (1/2) * expected number of times S_k > 0: 1 <= k <= 2n. By linearity of expectations, expected number of times S_k = 0: 1 <= k <= 2n is simply sum_{k=1}^{2n} P{S_k = 0 | S_{2n} = 0} = sum_{k=1}^n P{S_{2k} = 0 | S_{2n} = 0}. Now P{S_{2k} = 0} = binomial{2k, k}/2^{2k} so: P{S_{2k} = 0 | S_{2n} = 0} = P{S_{2n} = 0 | S_{2k} = 0}P{S_{2k} = 0}/P{S_{2n} = 0} = binomial{2(n - k), n - k}binomial{2k, k}/binomial{2n, n}. A standard identity for binomial coefficients tells us that sum_{k=0}^n binomial{2(n - k), n - k}binomial{2k, k} = 2^{2n} so our expected winnings are given by n + (1/2)(2^{2n}/binomial{2n, n} - 1) = n - 1/2 + 2^{2n - 1}/binomial{2n, n} which matches with the expression Michael quoted above. A little bit of extra work gives the more general result. --Richard
On Wednesday, December 26, 2018, 9:07:08 PM PST, Tomas Rokicki < rokicki@gmail.com> wrote:
Heh, I should have done the algebra! Nice find.
Knuth's Concrete Math taught me a lot of neat tricks for working with binomials; I should have taken this opportunity to try them out.
That solution (for n=m) is remarkably concise.
-tom
On Wed, Dec 26, 2018 at 9:01 PM Michael Kleber <michael.kleber@gmail.com
wrote:
Neat question!
Google search for the exact answer (3724430600965475/123979633237026, as Tom said) turns up a hit in Russian; translation at
https://translate.google.com/translate?hl=en&sl=ru&u=https://habr.com/users/...
Ah, and Google search for just the numerator yields a hit on https://www.jstor.org/stable/2687606. Registering for a free JSTOR account, that URL shows me that this was Problem #630, "Guessing Card Colors", appearing with solution in The College Mathematics Journal
Vol.
30, No. 3 (May, 1999), pp. 234-235. The problem was posed my Michael Andreoli, Miami-Dade Community College (North), Miami, FL, and the published solution was by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA. Andreoli's formulation of the problem there presupposes that you always guess the more-likely color (and guess randomly when tied), which as Cris says is optimal.
Steelman proves that for m red cards and n black cards with m >= n, the expected value is
E(m,n) = m + sum{k=0..n-1} binomial(m+n,k)/binomial(m+n,n)
The proof is by induction on m+n. When m=n, this simplifies to
E(n,n) = n - 1/2 + 2^(2n-1)/binomial(2n,n)
Ah: And there's an editor's note that one of the solvers (Michael Vowe of Therwil, Switzerland) pointed out that this is a special case of Problem #4661 from the American Math Monthly, vol 63 (1956), pp. 51-53. But I haven't tried to track down the AMM article to see what the generalization is -- maybe to drawing marbles out of an urn with more than 2 colors?
--Michael
On Wed, Dec 26, 2018 at 6:10 PM Dan Asimov <dasimov@earthlink.net> wrote:
Although I believe this:
----- Hmm, strategy seems clear: guess the majority color remaining, if any -----
, I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times?
Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant.
On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang.
You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end.
Instead, what if the winner is defined to be *the one who was *leading* more*.
Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other.
If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties?
Now: Onward, to the third-order effects.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Thanks! Fixed! Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Dec 27, 2018 at 5:51 PM Michael Kleber <michael.kleber@gmail.com> wrote:
Neil: those sequences are about a 2n-card deck, not an n-card deck.
--Michael
On Thu, Dec 27, 2018 at 12:02 PM Neil Sloane <njasloane@gmail.com> wrote:
The numerators and denominators of E(n,n) are now A322755, A322756. (The latter is twice A001790.)
On Thu, Dec 27, 2018 at 1:30 PM Richard Chatwin via math-fun < math-fun@mailman.xmission.com> wrote:
This is fairly straightforward when considered in terms of a random walk where the position S_k of the random walk at stage k represents the difference between the numbers of red and black card remaining. As previously discussed an optimal strategy always chooses red when S_k > 0, black when S_k < 0 and randomly chooses when S_k = 0. By mirroring any path, we have that S_k is always nonnegative. When S_k > 0 we guess red and we will be correct and win a dollar whenever the random walk takes a downward step.
Starting from S_0 = 0 and ending at S_{2n} = 0, there must be n downward steps so we win n dollars. In addition, whenever S_k = 0, we win a dollar with probability 1/2. So our total winnings are n + (1/2) * expected number of times S_k > 0: 1 <= k <= 2n. By linearity of expectations, expected number of times S_k = 0: 1 <= k <= 2n is simply sum_{k=1}^{2n} P{S_k = 0 | S_{2n} = 0} = sum_{k=1}^n P{S_{2k} = 0 | S_{2n} = 0}. Now P{S_{2k} = 0} = binomial{2k, k}/2^{2k} so: P{S_{2k} = 0 | S_{2n} = 0} = P{S_{2n} = 0 | S_{2k} = 0}P{S_{2k} = 0}/P{S_{2n} = 0} = binomial{2(n - k), n - k}binomial{2k, k}/binomial{2n, n}. A standard identity for binomial coefficients tells us that sum_{k=0}^n binomial{2(n - k), n - k}binomial{2k, k} = 2^{2n} so our expected winnings are given by n + (1/2)(2^{2n}/binomial{2n, n} - 1) = n - 1/2 + 2^{2n - 1}/binomial{2n, n} which matches with the expression Michael quoted above. A little bit of extra work gives the more general result. --Richard
On Wednesday, December 26, 2018, 9:07:08 PM PST, Tomas Rokicki < rokicki@gmail.com> wrote:
Heh, I should have done the algebra! Nice find.
Knuth's Concrete Math taught me a lot of neat tricks for working with binomials; I should have taken this opportunity to try them out.
That solution (for n=m) is remarkably concise.
-tom
On Wed, Dec 26, 2018 at 9:01 PM Michael Kleber < michael.kleber@gmail.com
wrote:
Neat question!
Google search for the exact answer (3724430600965475/123979633237026, as Tom said) turns up a hit in Russian; translation at
https://translate.google.com/translate?hl=en&sl=ru&u=https://habr.com/users/...
Ah, and Google search for just the numerator yields a hit on https://www.jstor.org/stable/2687606. Registering for a free JSTOR account, that URL shows me that this was Problem #630, "Guessing Card Colors", appearing with solution in The College Mathematics Journal
Vol.
30, No. 3 (May, 1999), pp. 234-235. The problem was posed my Michael Andreoli, Miami-Dade Community College (North), Miami, FL, and the published solution was by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA. Andreoli's formulation of the problem there presupposes that you always guess the more-likely color (and guess randomly when tied), which as Cris says is optimal.
Steelman proves that for m red cards and n black cards with m >= n, the expected value is
E(m,n) = m + sum{k=0..n-1} binomial(m+n,k)/binomial(m+n,n)
The proof is by induction on m+n. When m=n, this simplifies to
E(n,n) = n - 1/2 + 2^(2n-1)/binomial(2n,n)
Ah: And there's an editor's note that one of the solvers (Michael Vowe of Therwil, Switzerland) pointed out that this is a special case of Problem #4661 from the American Math Monthly, vol 63 (1956), pp. 51-53. But I haven't tried to track down the AMM article to see what the generalization is -- maybe to drawing marbles out of an urn with more than 2 colors?
--Michael
On Wed, Dec 26, 2018 at 6:10 PM Dan Asimov <dasimov@earthlink.net> wrote:
Although I believe this:
----- Hmm, strategy seems clear: guess the majority color remaining, if any -----
, I'm a lot less sure of the rarish case when it's a tie: Is it wiser to, say, alternate your guesses when it's a tie (to pick up, you know, a second-order advantage, now that you have maxed out your first-order advantage), or is it entirely irrelevant (to your expected gain) what you pick at those times?
Actually, now that I'm writing it, I kind of sort of *think* that it is completely obvious that it's entirely irrelevant.
On the other hand, suppose that instead of only considering the *expected* value of this game we view it as a 2-player thang.
You are playing against an opponent — each playing in isolation from the other — but with the winner being *not* necessarily the person who is ahead by the end.
Instead, what if the winner is defined to be *the one who was *leading* more*.
Where a scorekeeper has a running tally of each player's progress through the game. Each player gets one metapoint for each completed t'th stage during the ordinary game, 1 <= t <= 52, at which they are strictly ahead of the other.
If at the end of the game *leading more* (i.e., having the most metapoints) were the only thing that mattered, would that affect strategy at ties?
Now: Onward, to the third-order effects.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
Michael Kleber -
Neil Sloane -
Richard Chatwin -
Tomas Rokicki