Skip to main content
discribed the idealized riffle shuffle precisely
Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the pile, we pull three cards off the top of the deck and put them in the pile. If KH is in the pile, we riffle shuffle the deck and the pile together. I will assume the mathematically idealized riffle shuffle where the order of cards within the deck and the pile do not change, but all possible ways of shuffling them together with this constraint are equally likely.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and in the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P+1}+1$ (one card from the pile and $2\frac{52-P}{P+1}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P+1}+1$$ or $P \approx 9.8$.

One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that $k$ is probably too small to be equally likely to be one of the three residues mod 3. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

UPDATE: improved estimate slightly

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the pile, we pull three cards off the top of the deck and put them in the pile. If KH is in the pile, we riffle shuffle the deck and the pile together.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and in the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P+1}+1$ (one card from the pile and $2\frac{52-P}{P+1}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P+1}+1$$ or $P \approx 9.8$.

One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that $k$ is probably too small to be equally likely to be one of the three residues mod 3. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

UPDATE: improved estimate slightly

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the pile, we pull three cards off the top of the deck and put them in the pile. If KH is in the pile, we riffle shuffle the deck and the pile together. I will assume the mathematically idealized riffle shuffle where the order of cards within the deck and the pile do not change, but all possible ways of shuffling them together with this constraint are equally likely.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and in the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P+1}+1$ (one card from the pile and $2\frac{52-P}{P+1}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P+1}+1$$ or $P \approx 9.8$.

One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that $k$ is probably too small to be equally likely to be one of the three residues mod 3. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

UPDATE: improved estimate slightly

Improved estimate slightly
Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the second pile, we pull three cards off the top of the deck and put them in the second pile. If KH is in the second pile, we riffle shuffle the pilesdeck and the pile together.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and in the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P}+1$$2\frac{52-P}{P+1}+1$ (one card from the pile and $2\frac{52-P}{P}$$2\frac{52-P}{P+1}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P}+1$$$$ P-1 =k = 2\frac{52-P}{P+1}+1$$ or $P \approx 10.2$$P \approx 9.8$.

This isn't quite right ... I'll come back and edit it later. One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that I'm not exactly sure about the $2\frac{52-P}{P}$, but this second piece I should$k$ is probably too small to be ableequally likely to getbe one of the exact expression forthree residues mod 3. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

UPDATE: improved estimate slightly

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the second pile, we pull three cards off the top of the deck and put them in the second pile. If KH is in the second pile, we riffle shuffle the piles together.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P}+1$ (one card from the pile and $2\frac{52-P}{P}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P}+1$$ or $P \approx 10.2$.

This isn't quite right ... I'll come back and edit it later. One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that I'm not exactly sure about the $2\frac{52-P}{P}$, but this second piece I should be able to get the exact expression for. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the pile, we pull three cards off the top of the deck and put them in the pile. If KH is in the pile, we riffle shuffle the deck and the pile together.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and in the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P+1}+1$ (one card from the pile and $2\frac{52-P}{P+1}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P+1}+1$$ or $P \approx 9.8$.

One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that $k$ is probably too small to be equally likely to be one of the three residues mod 3. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

UPDATE: improved estimate slightly

Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the second pile, we pull three cards off the top of the deck and put them in the second pile. If KH is in the second pile, we riffle shuffle the piles together.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P}+1$ (one card from the pile and $2\frac{52-P}{P}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P}+1$$ or $P \approx 10.2$.

This isn't quite right ... I'll come back and edit it later. One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that I'm not exactly sure about the $2\frac{52-P}{P}$, but this second piece I should be able to get the exact expression for. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.