Wikipedia:Reference desk/Archives/Mathematics/2007 June 24

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 24

Shuffling

I heard something about odds that I don't think is right, but I'm not sure I've worked it out correctly. Here's how you set it up: Get a deck of cards, and have someone shuffle it thoroughly. Ask them to name two numbers Ace through King (like Jack and 5, say). Bet them that a Jack and a 5, somewhere in the deck, have at most one card between them. The claim is that you have more than a 99% chance of winning that bet. I think the odds of winning would be less than 82%, probably a fair bit less. What do you think? Black Carrot 00:06, 24 June 2007 (UTC)

Well, you have 16 different jack+five pairs. The probability of a given five being separated by zero or one cards from a given jack is approximately 4/52. The probability of none of the 16 pairs being that close is approximately (1-4/52)¹⁶. So I would say the probability you are looking for should be approximately 1-(1-4/52)¹⁶~72.2%. Taking into account end-of-deck effects, but still approximating the pairs as independent, I end up with 1-(1-202/52²)¹⁶~71.1%. --mglg_(talk) 01:21, 24 June 2007 (UTC)

While the magnitude there sounds about right, I would point out that those 16 pairs are strongly non-independent, most notably that other Js and 5s can be between any one particular pair of them!. This suggests looking at the pairs in a consecutive fashoin, where there are only seven pairs, and the only non independence is that a card between one such pair cannot be between another.

The 8 Js and 5s are in a certain order, and in between them are 7 gaps, with two gaps on either end. To lose the bet for any ordering of those 8, each of the inner 7 gaps need to have at least 2 other cards in it. One can combinatorially compute how many all the gaps are filled up with two cards. For any assignment of pairs of cards to the gaps, one can combinatorially compute how many ways the rest of the cards can be inserted anywhere (including at the ends). Thus the number of shuffles which lose is a product of three terms: # orderings of the 8 cards, # ways separating all 7 adjacent pairs, # ways to insert the rest. Then divide into the total number of ways to arrange 52 cards and subtract from one. There may be other ways of breaking the problem down into independent nested binnings which are easier to calculate, but I strongly suspect that considering the 8 cards sequentially like this will makes things loads easier. Baccyak4H (Yak!) 02:41, 24 June 2007 (UTC)

See, the thing about that is, getting an accurate answer would take a lot of work (even more than Baccyak suggests, since in many orderings of the 8 cards two of the same could land right next to each other) and most answers I could get including the word "about" seem a bit vague. It's hard to tell how close they'd land. So, I tried to get a strict upper bound on it. The way I saw it, we could assume the Jacks had been placed first, then place the 5s. There are four Jacks, and at most 16 cards within two of a Jack, meaning at least 32 remaining. Placing the first 5, the odds are 32/(16+32)=2/3 that it would land away from the Jacks. Assuming all of them landed away from Jacks, the odds for each would be the same but with the 32 (the count of cards still unclaimed that aren't near Jacks) going down once each time. Their product, the lower bound on the odds of losing the bet, would be 1798/9729 = 0.1848, putting an easy upper bound on the odds of winning at 82%. Does that sound right? Black Carrot 03:17, 24 June 2007 (UTC)

I agree with your upper bound, Black Carrot – I just came back here to enter the same thing! I was going to express it as $1-{\binom {32}{4}}/{\binom {48}{4}}={\frac {7931}{9729}}\approx 81.52\%$. As you say, the exact answer is likely to be considerably lower than this, because there are large probabilities of having less than 16 "winning slots" free after placing the jacks. But the upper bound suffices to prove that the "99%" claim is false. --mglg_(talk) 04:12, 24 June 2007 (UTC)

Thanks. Great minds think alike, I guess. :) Black Carrot 04:25, 24 June 2007 (UTC)

That, of course, being equally true about mediocre minds... --mglg_(talk) 04:38, 24 June 2007 (UTC)

I've run a simulation and, modulo mistakes in my implementation, the result is around 73.5%. -- Meni Rosenfeld (talk) 11:06, 24 June 2007 (UTC)

Wow, he hit it about on the head. I've been trying to work it out Baccyak's way, but the result I've gotten is a bit hard to believe. I should have gotten a much tighter upper bound, but instead I got that the odds of winning are strictly less than 94%. I'd like someone to check my work. I get the number of ways of placing eight cards in eight spots as 8!, the number of ways of choosing 14 cards from what remains as (44 C 14), the number of ways of arranging those between the original 8 as 14!, the number of ways of placing the remaining 30 cards as f(30) to be defined in a moment, and the number of ways of ordering those 30 as 30!. The total number of orderings that would lose is greater than that, because it counts nothing that does not lose but leaves out situations where cards of the same type (5 and 5, say) can be closer than two from each other. However, it seems like it should provide a tighter bound than the previous one, because it counts all the same cases and more. f(30) is the number of ways of dropping 30 identical pegs into 9 baskets, which would be a Figurate number of 8 dimensions and length 31. That makes it equal to (38!/30!)/8!. The total product, divided by 52!, simplifies to 44!38!/(52!30!), about 6.5%. Black Carrot 13:29, 24 June 2007 (UTC)

The way I looked at it (to find the upper bound) is to first assume the jacks are evenly spaced, so there are 4 different cards near each jack. This gives us a total of 16 cards of the remaining 48 non-jacks which we're concerned with. The chances that each five will be in those 16 cards is thus 16/48 = 1/3. The chance that each five is not one of those 16 cards is therefore 2/3. This gives us the probability that none of the 4 fives is near a jack as (2/3)⁴ or 16/81 = 19.75%, and the P that one or more five is near a jack is 80.25%. However, if we allow for the possibility that the jacks are near each other, or near the top or bottom of the deck, both would lower the probability of a nearby five to below 80%. StuRat 01:27, 25 June 2007 (UTC)

StuRat, your result is an approximation of the upper bound that has already been reported twice above. Your approximation is to ignore the fact that no more than one five can occupy the same position. This is why you get 65/81 instead of the exact answer 7931/9729 for the upper bound. --mglg_(talk) 01:50, 25 June 2007 (UTC)

Since the question was "is 99% correct" or possibly "is less than 82% correct", an exact answer is not needed, we only need to prove that 99% (or 82%) is above the upper bound to answer the question, which I have done. I believe my method was the simplest approximation which gave an answer accurate enough to answer this question (so simple, in fact, that you can do the math in your head). It is also helpful to confirm earlier answers, especially when using a slightly different method, as a check. StuRat 15:44, 25 June 2007 (UTC)

I can report an exact value for the probability of 3230755238/4389805875 = 0.735967678297..., which is consistent with Meni Rosenfeld's reported experimentally determined 73.5%. What I've done is count, for various lengths, the number of sequences (shuffle prefixes) for each of the patterns *···*@@, *···**J, *···**5, *···*J@, and *···*5@, in which * is any card, J is a Jack, 5 is a 5, and @ is any other card than Jack or 5; additionally, in the sequence no J and 5 must occur as neighbours or almost neighbours. Given all counts for length n for each of these patterns of the sequences with exactly u Js and v 5s, the same counts can be cheaply computed for length n+1. From the resulting data, with a little effort the probability can be determined.  --Lambiam^Talk 16:27, 25 June 2007 (UTC)

Thanks Lambiam! I knew you would come through and enlighten us in the end. --mglg_(talk) 17:55, 25 June 2007 (UTC)

I don't understand. Could you explain that a little more? Black Carrot 04:06, 26 June 2007 (UTC)

A rethink

Carrot, up above you came up with an approximation of about 6.5%, trying my line of reasoning. In hindsight, I realize the exact formulation I suggested was needlessly complicated, but nonetheless (IMO) still on the right track. I tried a rethink and want to share it here.

Forget which cards are which, except for a) eight target cards; b) the rest. This can be seen by noting your problem is isomorphic to selecting eight integers from 1 to 52 without replacement and seeing whether the smallest difference between any two integers is three or greater (three because there are two integers between integers that are three apart). I will tackle this formulation.

How many total ways can this be done, win or lose? This is 52 choose 8. Only the positions of the key cards matter here. Which particular key card is, e.g., J♥ or which non-key card is 2♣ is immaterial.

How can we enumerate the winning shuffles? Here, piggybacking on Lambiam's notation, let "*" be a key card (J or 5, in your example), let "x" be any single non-key card, and let "@" be any sequence (perhaps of length zero) of non-key cards. These are placeholders for the cards' positions, i.e., 1 to 52. Then a winning hand (does not have an interval of at most one card) can be enumerated as such (spacing for clarity):

@ *xx @ *xx @ *xx @ *xx @ *xx @ *xx @ *xx @ * @

Note the last "*" is not followed by "xx". (We could have written "@ xx* @ xx* ...", but the results will be the same.) The "*"s are exchangeable, as are the "x"s, so we can ignore their exact identity. Now each such winning shuffle (or sample of 8 numbers) is completely determined by the "@"s. These form a composition of (52 - 3*(8-1) - 1) = 30 into 9 parts, including the possibility of zeros (if two "*xx" are adjacent). The formula for the number of such compositions of n into r parts is (n + r - 1) choose (r - 1). In this case, it is 38 choose 8.

Thus the number of winning hands is

${\frac {\dbinom {38}{8}}{\dbinom {52}{8}}}$

which reduces to 479446 / 7377825 or about 6.49847%. The losing chance is thus about 93.50153%. I have done a simulation in R, and with 4000000 runs, am getting 6.5090% with SEM of 0.0123%. This is very close to your estimate above. (Code available on request—I am working to generalize this to any number of key cards from any size desk with any size gaps.)

An aside. The change of losing the bet if asked that there would be no cards adjacent to each other (that is, there was at least one card between each of the Js and 5s), then I get ~71.2% I wonder if this is what was really calculated elsewhere in several places. Baccyak4H (Yak!) 19:45, 26 June 2007 (UTC)

"This can be seen by noting your problem is isomorphic to selecting eight integers from 1 to 52 without replacement and seeing whether the smallest difference between any two integers is three or greater (three because there are two integers between integers that are three apart). " If I understand you correctly, this isn't correct, since you're counting, e.g., Jack-something-Jack as a successful hit. Donald Hosek 20:55, 26 June 2007 (UTC)

I think there's been a misunderstanding. If I challenged you to this, I would win if a Jack and a 5 were in close proximity (with about 73.5% likelyhood), and lose if no Jack was near a 5 (with about 26.5% likelyhood.) Whether a Jack is near a Jack, or a 5 near a 5, has no influence on the bet. That's why all the other analyses, except for my use of yours (which arrived at the same fraction you did :) ), specifically mentioned Jacks and 5s, in two groups of four. Black Carrot 02:46, 27 June 2007 (UTC)

J-something-J is a win for the poser (you lose!). There are 8 Js and 5s (in this case) total. Do not be confused between Js and 5s. Here, the important distinction is between 8 key cards (both Js and 5s in your example) and the rest. If (say) 2 Js were only one card apart, you would lose. But you would as well if 2 5s were only one card apart, or any J and 5. Thus you can look at the 4 Js and 4 5s as being from a group of 8 "key" cards. I am reading Carrot's reply to be questioning of Donald's conclusions; if so, I agree.

Can anyone point out a flaw in my reasoning? If not, I can provide a general solution (as alluded to above) to the probabilities of winning such a generalized bet. Baccyak4H (Yak!) 03:24, 27 June 2007 (UTC)

Um, no. Black Carrot's reply (as well as his original problem statement) confirms Donald's observations, and questions yours. You win if at any place there are a J and a 5 (not J and J or 5 and 5) close to each other (separated by at most one card). So the Js and the 5s are different, you can't treat them as just "8 key cards". -- Meni Rosenfeld (talk) 07:33, 27 June 2007 (UTC)

Mystery Series

Something came up on a Facebook forum, and I can't remember the answer to it. Well, I can, but it seems I'm remembering it wrong. Imagine a tower of identical bricks, each shifted to the right as far as it will go without falling off. In other words, the center of balace of each is right on the edge of whatever it's sitting on. How far over is each one, and how far does the tower extend to the side? I remember it being an example of the harmonic series in action, and I remember the result being that, given an impractically tall tower, you can extend the right edge arbitrarily far. I'm working it out now, though, and I'm getting the displacement of each to be 1/2^n from the one below it, with the result that you can never get even a block's length away from the base. As this is patently false, experiment being my guide, I have to assume I made a mistake somewhere. Any ideas? Black Carrot 23:58, 24 June 2007 (UTC)

For the tower to have the maximum stable extension, the edge of each brick should coincide with the combined center of mass of all the bricks above it. If you work this out, brick n (from the top) will extend by 1/(2 n) beyond the brick below it, for unit length bricks. This means that the total overhang of an n-brick tower will be ${\frac {L}{2}}\sum _{k=1}^{n-1}{\frac {1}{k}}$, which does go to infinity with n, albeit very slowly. Not all sequences that start with 1/2 and 1/4 are 1/2ⁿ... --mglg_(talk) 00:36, 25 June 2007 (UTC)

The first Google hit on "harmonic series" bricks is http://www.antiquark.com/2005/04/harmonic-series-and-bricks.html which includes 2 nice pictures. I have seen the problem before and the Google search has many relevant hits. Maybe we should mention this nice problem somewhere (I searched shortly and couldn't find it in Wikipedia). PrimeHunter 00:45, 25 June 2007 (UTC)

On page 3 of the Google search I get:

"In response to a legal request submitted to Google, we have removed 1 result(s) from this page. If you wish, you may read more about the request at ChillingEffects.org."

I haven't seen such a message before. The link doesn't work for me. PrimeHunter 00:49, 25 June 2007 (UTC)

I found a name. Does somebody (not me) want to write Leaning tower of Lire? [1] Or maybe it should just be a section somewhere. PrimeHunter 01:02, 25 June 2007 (UTC)

In reality, I assume the weight of the bricks would creat an enormous amout of stress that would eventually break any material. nadav (talk) 01:31, 25 June 2007 (UTC)

That's what it was! Thanks. Black Carrot 03:35, 26 June 2007 (UTC)