|
|
Go to page [Previous] 1~2~3~4 [Next] | ||||||||||
R2D2 Veteran user 304 Posts |
Ok this just in: I computed it analyticly and the answer is indeed 0.486.
If anyone's interested I can give the mathematical details, but basically I had to write down a big recurrence relation. Nothing too elegant. |
|||||||||
RogerTheShrubber Veteran user 301 Posts |
Elegant or not, it's all miles above my ability to figure it out. I'd love the details if you can provide them without going to too much trouble. I'd also be interested in the Monte Carlo simulation you described.
|
|||||||||
R2D2 Veteran user 304 Posts |
Here goes... you actually don't need to know any fancy math for this. You just need some basic probability. But it gets tedious.
Suppose we want to know the probability of having a queen next to a king somewhere in the deck. (This is what I'll refer to as a "success".) Define the following functions: P(q,k,n) = probability of having a queen next to a king given that you have n cards left in the deck, q of which are queens, k of which are kings, and that the previous card you dealt was neither a queen nor a king. In other words, P is the probability of success given a certain mix of cards remaining. Note that n is the number of remaining cards, not the total number of cards. Let Q(q,k,n) = probability of success given that the previous card dealt was a queen. The variables are the same as for the function P. Notice that capital Q is a function and little q is a variable. Let K(q,k,n) = probability of success given that the previous card dealt was a king. The variables are the same as for the function P. Now the easy part: Figure out the base cases. P(0,k,n) = 0, i.e. if you have no queens left, you have a zero probability of success (since the previous card was neither a Q nor K.) P(q,0,n)=0, same reason as above. P(q,k,0)=0, (there are no cards left!) P(q,k,1)=0, i.e. you can't succeed if there’s only one card left. Q(q,0,n)=0, i.e. you need at least one king remaining (but not a queen – the previous card dealt was a queen after all) Q(q,k,0)=0, i.e. you need at least one card in order to succeed from here. K(0,k,n)=0, i.e. you need at least one queen remaining. K(q,k,0)=0, i.e. you need at least one remaining card. Now the moderately tricky part. Define the functions recursively. First let’s do Q(q,k,n). If the card you just dealt was a queen and you have n cards left, what are the ways you can succeed from here? Possibility 1: The next card you deal is a king. Probability of that is k/n. Possibility 2: The next card you deal is a queen, and then you succeed with the remaining n-1 cards. Probability of the next card being a queen is q/n, and the probability of success after that is Q(q-1,k,n-1). Overall probability: q/n * Q(q-1,k,n-1) Possibility 3: The next card is neither a queen nor a king. You then have n-1 cards left, and you succeed with the remaining n-1 cards. The probability of an indifferent card being next is (n-q-k)/n and the probability of success after that is P(q,k,n-1) (since you’d then be starting “fresh”). Overall probability: (n-q-k)/n * P(q,k,n-1). Total probability of success given that you just dealt a queen = Q(q,k,n) = k/n %2B q/n * Q(q-1,k,n-1) %2B (n-q-k)/n * P(q,k,n-1) Yes, this is a recursive function, but all the recursive evaluations involve smaller parameter values, and the whole computation bottoms out eventually (because of the base cases). If you've gotten this far, then you’re past the worst of it. You now define K(q,k,n) similarly are you get: K(q,k,n) = q/n %2B k/n * K(q,k-1,n-1) %2B (n-q-k)/n * P(q,k,n-1) This also follows by symmetry. (The role of the kings and queens are interchangeable.) Finally, we define P(q,s,n). Recall that this is the probability of success from a new deck of n cards, or equivalently from a deck with n cards remaining but where the previous card was neither a king nor a queen. Here are the three cases to consider: Possibility 1: The next card you deal is a king and then you succeed from there. Probability of that is k/n * K(q,k-1,n-1) Possibility 2: The next card you deal is a queen and then you succeed from there. Probability of that is q/n * Q(q-1,k,n-1) Possibility 3: Next card is indifferent. Just like possibility 3 from earlier: (n-q-k)/n * P(q,k,n-1) Therefore: P(q,k,n) = k/n * K(q,k-1,n-1) %2B q/n * Q(q-1,k,n-1) %2B (n-q-k)/n * P(q,k,n-1) Now you just write a computer program that codes up these three functions and you evaluate P(4,4,52). The one complication that comes up is that the recursion branches into a *huge* tree. Each function call results in two other function calls, and n only drops by 1 each time! I think it's basically intractable unless you shorten the computation somehow. Here's how I fixed that: I cached the values of K, Q, and P so that I never had to evaluate these for the same parameters twice. Huge, huge savings. (I suppose this is equivalent to doing the whole thing with dynamic programming, for those of you who are familiar with that.) Look at the first term of P: k/n * K(q,k-1,n-1). Clearly if k is zero, there's no need to evaluate K(q,k-1,n-1). You can make this optimization in every instance of a recursive call, i.e. before you recurse, check the coefficient to see if it’s zero. This results in a small speedup. Finally, the formulas for Q and K are symmetric. So if you fill in the cache for the value of (for instance) Q(3,2,10) then you can also fill in the value for K(2,3,10). This also gives you a small speedup. Once you make these optimizations, the whole things runs really fast, and it spits out 0.486. I realize this looks long and complicated, but it's really just a long sequence of simple ideas. Let me know if anything here is unclear. -- You also asked about the Monte Carlo sim. For this, I really just used a brute force approach. For each trial, I randomly picked positions for the kings and queens, making sure that they were distinct. Then I checked to see if any of the king positions differed from any of the queen positions by 1. Repeat 1 million (or 10 million) times. I can post code if you’re really curious. P.S. If you're wondering how I got a plus sign to appear despite the BBCode parser, I just typed percent then 2 then capital B. |
|||||||||
R2D2 Veteran user 304 Posts |
Arghh.... using percent-2-B worked in preview mode (it showed up as a plus sign).
So if you're having trouble understanding my formulas, mentally convert that to a plus sign. Why does this have to be so difficult? |
|||||||||
R2D2 Veteran user 304 Posts |
This is much easier to understand in pdf form (see attached).
Click here to view/download attached file. |
|||||||||
RogerTheShrubber Veteran user 301 Posts |
R2D2, thanks very much for all of this. The math is still miles above my head, but I really appreciate being able to see it.
Cheers, Roger |
|||||||||
R2D2 Veteran user 304 Posts |
No problem, Roger. And if you're ever in NYC I'd be happy to meet up and take you through it. 😀
|
|||||||||
RogerTheShrubber Veteran user 301 Posts |
I'll probably be in NYC once or twice between now and the end of the year, but I'd be lying if I said I'd be able to follow the math. When I went to high school we were allowed to drop math after one year and I was dumb enough to do just that. Did the absolute minimum on math in college, too. One of my bigger regrets, especially thinking at the time how great it was that I didn't have to do more.
|
|||||||||
alecStephenson New user 69 Posts |
There is a way of calculating this without recursion but it's not easy.
Let C(n,r) be n!/(r!(n-r)!). Let p be the plus sign and * be multiplication. Ignoring suits, there are C(52,4) ways to place the Qs and then C(48,4) ways for the Ks. So there are C(52,4) * C(48,4) = 52677670500 possibilities in total. It is easier to first work out the number of cases where a Q and a K are NOT adjacent. If the four Qs are in the deck, there are up to 8 adjacent spots for the Ks. Suppose there are 8 - Z adjacent spots where Z is in 0,1,...,7. For example, if the four Qs are in the first four places then Z = 7 because there is only one adjacent spot. If there are Z spots, then there are C(40 p Z,4) possibilities where the Kings will NOT be adjacent to any Q. Now the tricky part. How many possible positions for the Qs are there for each Z ? Suppose A is the number of pairs of queens, so A is in 0,1,2,3. So for two pairs or for three-of-a-kind, A = 2, and for four-of-a-kind A = 3. Suppose B is the number of times there is a single card (exactly one card) between two Qs; also, add one if a Q is in the 1st position and add one again if a Q is in the 52nd position. This means that Z = 2*A p B. For a fixed Z, the number of positions for the Qs is C(3, A) * C(5-A, B) * C(44 p A, 4 - A - B) where the sum is over the pairs (A,B) such that Z = 2*A p B. The C(3, A) term corresponds to the choices of paired Qs, the C(5-A, B) term corresponds to the choices of single cards between Qs (or Qs at the 1st or 52nd pos). The C(44 p A, 4 - A - B) term is the others. Now multiply this by C(40 p Z, 4), sum over Z = 0,...,7, and you get 27091923270. The fraction 27091923270/52677670500 reduces to 300684703/585307450. So the answer is one minus this, which is 284622747/585307450 = 0.486279. |
|||||||||
alecStephenson New user 69 Posts |
Corrections:
"If there are Z spots" should be "if there are 8-Z spots" "the number of positions for the Qs is" should be "the number of positions for the Qs is the sum of" Simulating is probably a better idea though... |
|||||||||
R2D2 Veteran user 304 Posts |
Quote:
On Oct 26, 2015, alecStephenson wrote: I disagree. Your solution rocks! I think you won the thread. Very clever approach. |
|||||||||
alecStephenson New user 69 Posts |
Thanks R2.
One more (hopefully!) typo correction: 27091923270 should be 27061623270 in both cases. For some reason I typed 9's rather than 6's. |
|||||||||
WilburrUK Veteran user 389 Posts |
Quote:
On Oct 26, 2015, R2D2 wrote: Seconded. Proof trumps simulation in my book. |
|||||||||
Terrible Wizard Inner circle 1973 Posts |
So are the actual odds less than fifty-fifty? Sorry for being dumb ...
|
|||||||||
R2D2 Veteran user 304 Posts |
Yes, less than 50%. It's 48.6%. Not a dumb question; there was a lot to wade through!
|
|||||||||
Terrible Wizard Inner circle 1973 Posts |
Sounds too risky to do on the radio ...c
|
|||||||||
RogerTheShrubber Veteran user 301 Posts |
I'm certainly not qualified to refute the math, but Lovell says it's about 75% and my results have been even higher. Never before has such an informative series of answers to anything left me more confused. I can't help but think that Lovell would have noticed if the probability was a little less than half, but again, the math is above my head and the calculations here seem very solid. I've never suffered from headaches before but I'm starting to get one now
|
|||||||||
R2D2 Veteran user 304 Posts |
Quote:
On Oct 30, 2015, RogerTheShrubber wrote: In that case, we probably misunderstood the question. Let me know if I'm stating it correctly. 1. Pick two ranks (e.g. Kings and Queens). 2. Look through the deck to see if there is a K next to a Q (in either order). You're asking the probability that this happens at least once. Is that correct? |
|||||||||
alecStephenson New user 69 Posts |
Interesting.
To recap, TomasB and R2's simulation, R2's recursion methodology and my working, have shown that the chance is 48.6%. As for the book, I have now found the part: it is under the TWO CARDS TOGETHER section. And RogerTS is correct - the quote in my edition is "Think of two card values. Not suits, just values. So you may think of K or 3 ot 5 and 9 for example. [...] I'll bet you even money that in that deck, right here and right now, two cards of the values you are thinking of will be together in that deck. The odds are heavily in my favor that they will be so." Firstly, it's a great book, and a really great and easy read, and also communicates the basics of odds calculations. But the author has simply made a mistake here. It is understandable: most odds things in the book are either fairly straightforward (to a maths/stats person) or they are complex but based on well known statistical problems (bithday problem, coupon matching etc). In this case, it is neither. It is a tricky problem that you are unlikely to find in any standard probability textbook. |
|||||||||
alecStephenson New user 69 Posts |
RogerTS: On your experiments, I can think of two possible explanations.
The second one is perhaps more likely. 1) You said that you run through the deck lightning fast. You may have identified cards as being together when they are not. 2) You are doing the experiments one after the other without shuffling numerous times between experiments. This means that the outcome of one experiment will be related to the outcome of the next one(s), particularly if you are using the same two ranks each time. For example if a K and Q are together and then you OH shuffle, they will probably still be together after the shuffle (a bit like when you have a k*y c**d and let the spectator shuffle). |
|||||||||
The Magic Cafe Forum Index » » All in the cards » » What are the odds of this (Simon Lovell "trick")? (0 Likes) | ||||||||||
Go to page [Previous] 1~2~3~4 [Next] |
[ Top of Page ] |
All content & postings Copyright © 2001-2024 Steve Brooks. All Rights Reserved. This page was created in 0.05 seconds requiring 5 database queries. |
The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement < |