beachbumbabs
Joined: May 21, 2013
• Posts: 14234
January 20th, 2014 at 10:07:30 PM permalink
Still having a problem understanding how the bounded groups will know they are correctly organized as WBBB or BBBW if they can't see their own and can't communicate (nobody else can order them correctly). Are you assuming that in a large enough room, that opportunity will randomly emerge?
If the House lost every hand, they wouldn't deal the game.
24Bingo
Joined: Jul 4, 2012
• Posts: 1348
January 20th, 2014 at 10:24:18 PM permalink
Basically, yes. Note that in all the answers, each group either has one correct answer or many wrong answers - it's sort of like the Martingale, where without affecting the expected value you usually win because when you do lose, you lose massively. By going bigger and bigger, we can get this to converge to a situation where the expected number of failures is still infinite, but the probability of even one can be made arbitrarily low.

ADDENDUM: Error, one sec. (Forgot the two.)

There we go. I'm going to work out an upper-bound with Σ2/k2 * ln(1-2k0) * 2k0, by calculating the first as its ultimate sum, π2/3, less the omitted terms.

According to the ever-reliable Google calculator.

1 - e^((pi^2/3 - 2*(1 + 1/4 + 1/9 + 1/16 + 1/25 + 1/36 + 1/49 + 1/64 + 1/81 + 1/100 + 1/121 + 1/144 + 1/169 + 1/196 + 1/225 + 1/256 + 1/289 + 1/18^2 + 1/19^2)) * ln(1-1/2^20)*2^20) = 0.09745948224

So starting at 2,621 groups of 20 wizards each gives a failure rate of under 9.746%. (The floor function, at this point, could only affect the sum by a factor of .00000095367.)
The trick to poker is learning not to beat yourself up for your mistakes too much, and certainly not too little, but just the right amount.
CrystalMath
Joined: May 10, 2011
• Posts: 1907
January 20th, 2014 at 10:42:00 PM permalink
Quote: beachbumbabs

Still having a problem understanding how the bounded groups will know they are correctly organized as WBBB or BBBW if they can't see their own and can't communicate (nobody else can order them correctly). Are you assuming that in a large enough room, that opportunity will randomly emerge?

Yes. They will stand in a line. If anyone can look back and see this pattern anywhere before them, then they know that pattern has been found and they will check if they are part of the next pattern. My method ensures that someone in the group will recognize that they are in the group without any communication. Also, because it is an infinite line, all patterns will eventually occur.
I heart Crystal Math.
Canyonero
Joined: Nov 19, 2012
• Posts: 509
January 21st, 2014 at 12:30:43 AM permalink
Quote: CrystalMath

Here's my solution:

Start with a target group of wizards of size 40. The first group will be the first group that is bounded by BBBW on one end and WBBB on the other end and contains 40 wizards between the bounds. The 40 wizards must be all W, with the exception of up to 2 B. Not all wizards in the group will know they are part of the group, but all wizards coming after the group will know that that group has been spoken for.

Each wizard will assume that he is part of the group if he is surrounded by 39 W and up to 1 B and those wizards are bounded by BBBW and WBBB (so, all together, there will be 42 W wizards with the exception of 1 or 2 B wizards. Any wizard who sees exactly 1 B in the group will guess that he is B.

The options are:

case 1: BBBW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WBBB
case 2: BBBW WWWWWWWWWWWWBWWWWWWWWWWWWWWWWWWWWWWWWWWW WBBB
case 3: BBBW WWWWWBWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWW WBBB

case 1: all wizards will abstain
case 2: all of the W wizards will guess incorrectly and the B wizard will abstain
case 3: the B wizards will guess correctly and the W wizards will abstain (the W wizards won't even know they are in the group, because they see 2 B to start with)

In cases 2 and 3, the B wizards can be located anywhere inside the 40 inner wizards, so we need to calculate the number of ways they can be ordered (or look at Pascals Triangle).

case 1: 1
case 2: 40
case 3: combin(40,2) = 780

p(correct guess) = 780/(780 + 40 + 1) = 95.0061%

Then, do this for group sizes 80, 160, 320...40*2^n. This will converge to 90.34% success rate.

I am convinced (which is not saying a lot). The groups are still random (so the probability of a correct guess actually applies for once) but well defined. I have been trying to put the two B wizards in a position that messes up the group from someones perspective, without success. Excellent!
CrystalMath
Joined: May 10, 2011
• Posts: 1907
January 21st, 2014 at 6:48:34 AM permalink
Thanks, Canyonero.

Here's another solution using the 20 wizard group:

Same as previous, but join the group if you see only 19 W wizards, bounded by BBW and WBB, then guess that you are a B wizard. If you are a single B wizard surrounded by W wizards, then the W wizards won't know they are in the group and will abstain, while the B wizard will guess correctly. If all of the wizards are W, they will incorrectly guess.

The probability of answering correctly is 20/21. Then do this for group size 40, 80, 160...
I heart Crystal Math.
MathExtremist
Joined: Aug 31, 2010
• Posts: 6526
January 21st, 2014 at 9:15:19 AM permalink
Quote: CrystalMath

Thanks, Canyonero.

Here's another solution using the 20 wizard group:

Same as previous, but join the group if you see only 19 W wizards, bounded by BBW and WBB, then guess that you are a B wizard. If you are a single B wizard surrounded by W wizards, then the W wizards won't know they are in the group and will abstain, while the B wizard will guess correctly. If all of the wizards are W, they will incorrectly guess.

The probability of answering correctly is 20/21. Then do this for group size 40, 80, 160...

Okay, here's my hangup. I understand the notion of grouping the wizards and using the guessing strategy to change the distribution of right/wrong guesses so that right guesses are spread out while wrong guesses are clumped together. That means each *group* has a high probability of being right.

However, the probability of any given guess being right is still only 50%. The groups that the wizards arrange themselves into are just arbitrary divisions. The OP did *not* say that the overall probability of success for the Wizards self-imposed groups had to be 90% or better; it said that 90% of the time "the wizards collectively win if, among them, there are an infinite number of correct guesses and zero wrong guesses." Regardless of the distribution of guesses into groups, the total number of guesses (per the problem statement) is infinite, and half of those guesses will be wrong. The wrong ones will be clustered into a much smaller number of groups than the right ones but that's irrelevant to the stated success criteria.

Bottom line: how is it possible for an infinite number of 50/50 trials ever to have zero failures, let alone 90% of the time?
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
CrystalMath
Joined: May 10, 2011
• Posts: 1907
January 21st, 2014 at 9:19:33 AM permalink
Quote: MathExtremist

Okay, here's my hangup. I understand the notion of grouping the wizards and using the guessing strategy to change the distribution of right/wrong guesses so that right guesses are spread out while wrong guesses are clumped together. That means each *group* has a high probability of being right.

However, the probability of any given guess being right is still only 50%. The groups that the wizards arrange themselves into are just arbitrary divisions. The OP did *not* say that the overall probability of success for the Wizards self-imposed groups had to be 90% or better; it said that 90% of the time "the wizards collectively win if, among them, there are an infinite number of correct guesses and zero wrong guesses." Regardless of the distribution of guesses into groups, the total number of guesses (per the problem statement) is infinite, and half of those guesses will be wrong. The wrong ones will be clustered into a much smaller number of groups than the right ones but that's irrelevant to the stated success criteria.

Bottom line: how is it possible for an infinite number of 50/50 trials ever to have zero failures, let alone 90% of the time?

I think that my new method for choosing the guessing wizards will result in an n/n+1 chance of choosing correctly. In dblanch's initial method of choosing the guessing wizards, there was a 50% chance of being correct, which would fail, undoubtedly.
I heart Crystal Math.
24Bingo
Joined: Jul 4, 2012
• Posts: 1348
January 21st, 2014 at 9:25:10 AM permalink
Quote: MathExtremist

Bottom line: how is it possible for an infinite number of 50/50 trials ever to have zero failures, let alone 90% of the time?

Again, think of the St. Petersburg game (i.e., flip a coin until the first tail - if it's on the first flip, you get nothing, the second, one unit, the third, two, the fourth, four, the fifth, eight, and so on). Infinite EV, but a 50% probability of no return, and you could easily come up with a version with a 90% probability of no return. By arranging the guesses such that there will be an increasing number of wrong guesses for every right one, thus causing the probabilities of wrong guesses to taper, we do essentially the same thing in reverse.
The trick to poker is learning not to beat yourself up for your mistakes too much, and certainly not too little, but just the right amount.
Canyonero
Joined: Nov 19, 2012
• Posts: 509
January 21st, 2014 at 10:11:16 AM permalink
Quote: MathExtremist

However, the probability of any given guess being right is still only 50%.

Crystalmath's solution avoids this problem IMHO, since the color of the guessing wizard's hat and the fact that he is indeed making a guess are not independent.

If a group that will contain a single guessing wizard is actually created, it is much more likely the wizard's hat will be the opposite of the majority, because there are much more ways a group like this could constitute itself. And yes, there will be an infinte amount of groups like this, but only the first group will actually guess. And the probability that this group has the setup that will lead to a correct guess is, as shown, 95%