Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have a deck of numbered cards (possibly with multiple copies of each number), perfectly shuffled, and you want to extract certain cards without disturbing the "shuffled-ness" of the remaining cards. This is easy to do in some cases. For instance, if you want to remove a unique card (the only $10$, say), or all cards with a particular number (all the $5$'s), then you can simply pull out the target cards while keeping the remaining cards in the same order. If all $n!$ permutations of the full deck were equally likely before, then all $(n-k)!$ permutations of the remaining $n-k$ cards are equally likely now; that is, the remaining cards are still shuffled. Similarly, if you remove the card in a pre-specified position (the topmost card, say) or set of positions (the bottom ten cards), then the remaining cards (whatever they are) will still be shuffled.

My question is about the cases where the simple approach doesn't work. For example, say you want to remove three of the four $7$'s (you don't care which ones). If you just pull out the topmost three $7$'s, then the remaining cards will clearly not be shuffled: the fourth $7$ isn't equally likely to be at any position, but rather is much more likely to be near the bottom of the deck. (The same problem occurs if you remove just one of the four $7$'s, but the bias is less extreme.) If you instead move cards from the top of the deck to the bottom, removing $7$'s as you find them until only one is left, then you have the opposite problem: the remaining $7$ is now likely to be near the top.

Is there any deterministic way to remove a single copy of a particular number without introducing a bias to the remaining cards?

(Note: Clearly there can't be one in general. For instance, if your cards are $\{1,2,2\}$, then there are three equiprobable deck configurations, and any mapping of these to the two target deck configurations $[1,2]$ and $[2,1]$ is going to have a bias. But are there non-trivial cases where it's possible?)

share|improve this question
    
Doesn't choosing a single 7 at random from among the 7s in the deck and removing it work? –  Steven Stadnicki Feb 13 '13 at 23:55
    
@Steven: It’s not deterministic. –  Brian M. Scott Feb 13 '13 at 23:56
1  
@BrianM.Scott Ahhh, fair point. Though turning my original point on its head, it seems like the question is precisely equivalent to 'is there a deterministic way of choosing one of the 7s at random?', since any deterministic scheme seems doomed to introduce bias on average... –  Steven Stadnicki Feb 13 '13 at 23:59
    
In your 1st paragraph, "if you want to remove a unique card (the only 10, say), or all cards with a particular number (all the 5's)..." how do you do this, do you read the deck in sequence until you encounter the specific card(s)? –  alancalvitti Feb 14 '13 at 0:13
    
I feel like you answered your own question. It's not possible in general. And it seems that whenever there are multiple indistinguishable copies of the same card, you're going to introduce bias (if you can't randomize). –  Greg Martin Feb 14 '13 at 0:48
show 6 more comments

3 Answers

up vote 3 down vote accepted

I'll consider the cases where you want to remove either one or all but one of $k$ indistinguishable cards. So assume you have $n$ cards of which $k$ are indistinguishable. It doesn't matter whether any of the others are also indistinguishable since their order will never change and their identity will never be used, so for simplicity let's assume that the remaining $n-k$ cards are all distinguishable.

To get an idea for a solution, let's first consider $k=2$. (In this case there's no difference between removing one or all but one of the two cards). There are $n!/2$ arrangements of the cards, and $(n-1)!$ arrangements after we've removed one, so we need to assign $n/2$ of the former to each of the latter. Obviously that's only possible if $n$ is even. (In your counterexample $n=3$ and $k=2$.)

As Greg pointed out, we can always choose some arbitrary assignment, so in a trivial sense the answer to your question is "yes", but a more interesting problem is to find a regular assignment that you can use in practice without memorizing exponentially many arrangements. For $k=2$, such an assignment is given by removing the first or second card depending on the parity of the distance between them.

To generalize this for $k\gt2$, we can reexpress it as removing or leaving a card determined by the remainder of the sum of the positions of all $k$ cards modulo $k$. It's not as clear as it was for $k=2$ whether this can lead to a regular uniform assignment. There is again the condition that the ratio of the arrangement counts is an integer. When removing one card, this is

$$\frac{n!/k!}{(n-1)!/(k-1)!}=\frac nk\;,$$

so there is a uniform assignment if $k\mid n$. When leaving one card, the ratio is

$$ \frac{n!/k!}{(n-k+1)!}=\frac1{n-k+1}\binom nk=\frac1{n+1}\binom{n+1}k\;, $$

which is often an integer and apparently always is an integer when $k\mid n$ (though I don't see why).

Each permutation $\pi$ of $[k]$ corresponds to a prescription to remove or leave the card with rank $\pi(r)$, where $r$ is the remainder of the sum of the positions of the cards modulo $k$. To explore which of these prescriptions lead to a uniform assignment, I wrote this code.

The results are rather interesting. In the case of removing one card, it seems that precisely the $k$ permutations $\pi_m(r)=m-r\bmod k$ (with $m\in[k]$) lead to a uniform assignment. For small $k$, this yields simple prescriptions that could be used in practice without a computer.

In the case of leaving one card, things are more complicated. There seem to always be permutations that lead to a uniform assignment if $k\mid n$. Sometimes all permutations do; up to and including $k=9$, this is the case for $n=2k$ if and only if $k$ is prime. But even if not all of them do, usually many more permutations lead to a uniform assignment than in the case of removing one card. This is true even if $k\nmid n$; in fact the only case that I found in which the integrality condition is satisfied but there are no admissible permutations is $n=11$, $k=6$.

share|improve this answer
add comment

Here's an example of a deck for which there exists such a deterministic procedure: a deck with two 1s and two 2s. Here is a deterministic procedure for removing exactly one 1 and preserving shuffledness:

  • If the two 1s are adjacent, then remove the first 1. (Of course it doesn't matter in this case which one you remove.)
  • If the deck is 1212, remove the second 1.
  • If the deck is 1221, remove the first 1.
  • If the deck is 2121, remove the second 1.
share|improve this answer
add comment

I found a nice solution for removing one of a pair (say, one of two $7$'s), so I'm answering my own question in that limited case. Let there be $n$ cards in the pile. Start flipping cards from the top (forming a second, face-up pile) until you find the first $7$, and remove it. Turn the second pile face-down, and finally, put the larger of the two piles on top of the smaller one. If $n$ is odd, then it's possible that the two piles will be exactly the same size; so this only defines a deterministic algorithm for even $n$. As @joriki's answer points out, that's the best you can do.

What's nice about this method is that you don't need to find the second $7$. Moreover, you don't really have to count anything, if you just eyeball which pile is larger. This would have some probability of error, of course, and it's not strictly deterministic if you don't count. But if (as seems likely) your eyeball function is symmetric (so $p_1(a,b)=p_2(b,a)$, where $p_i(a,b)$ is the probability that pile $i$ looks larger to you when there are $a$ cards in the first pile and $b$ in the second), then the final deck is still perfectly shuffled.

This solution works because there are exactly $n(n-1)/2$ initial configurations of the two $7$'s, and exactly $n/2$ of them lead to each of the $n-1$ final placements of the second $7$. (The second $7$ will wind up in position $k$ if the initial configuration was $[m,m+k]$ for $m\le n/2 \wedge m+k\le n$ or $[m,k+1]$ for $k+1>m>n/2$.) Placing the second $7$ uniformly at random is sufficient: the other cards may or may not get rotated, but their identities aren't used, so they stay shuffled.

I would love to know if there's a similar method for removing one of $k>2$ copies.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.