2
$\begingroup$

Imagine we have two people playing a game where they randomly sample playing pieces. Here are two ways the sampling can occur:

  1. Each player takes turns sampling without replacement from a central pile.
  2. The central pile is divided into a sub pile for each player. Each player then takes turns sampling without replacement from their own pile.

Are these scenarios meaningfully different? Would the players expect to see different sets of selected tokens under these different approaches?

The order in which the pieces are sampled is irrelevant; the only thing that matters is the set of pieces chosen by a player.

Thanks!

$\endgroup$
4
  • 1
    $\begingroup$ Is this sampling with replacement? $\endgroup$
    – Glen_b
    Dec 29, 2015 at 9:16
  • $\begingroup$ Without replacement. Sorry, I forgot to include that. $\endgroup$ Dec 29, 2015 at 18:39
  • $\begingroup$ This question is uninteresting when sampling with replacement, because it is obvious that eventually each player would almost surely have at least one of each type of piece in scenario (1) (search our site for "Coupon collector") whereas that is impossible in scenario (2). Conceivably the without replacement version of this question has multiple conflicting answers, depending on how the initial subdivision in (2) is carried out and how many pieces are drawn from each subpile. Could you provide those details? $\endgroup$
    – whuber
    Dec 29, 2015 at 18:58
  • $\begingroup$ whuber is right. You need to say HOW you create the sub piles. $\endgroup$
    – AlaskaRon
    Dec 30, 2015 at 21:44

2 Answers 2

1
$\begingroup$

Notation

Let the central pile have $N$ pieces. Suppose in case (1) that at the end of the sampling process, the players have chosen $k$ and $m$ pieces each, with $0 \le k+m \le N$. (Taking turns guarantees $|k-m| \le 1$, but that doesn't really matter.) Let's focus the analysis on the first player, anticipating that it will apply just as well to the second player.

Analysis of Case (1)

In case (1), any mechanism of blind random drawing assures that any particular set $P$ of $k$ pieces has the same chance of being drawn as any other such set. Since there are $$\binom{N}{k} = \frac{N!}{(N-k)!k!}$$ such sets, each has a probability of $1/\binom{N}{k}$ of being selected.

Analysis of Case (2)

In case (2), suppose the two piles $P_1$ and $P_2$ have $n$ and $N-n$ pieces respectively and that our first player is drawing her $k$ pieces from the first pile. Necessarily $k \le n$ and $m \le N-n$. There are only $\binom{n}{k}$ possible samples of $P_1$, each with equal probability.

There's an issue here: exactly how are the $N$ pieces divided into two piles? Maybe we can work out the necessary conditions. If the two sampling procedures (1) and (2) are to give equivalent results, then--putting the previous answers together--every particular sample $P$ of $k$ pieces must have a chance

$$\Pr(P\subset P_1) = \binom{k}{n}/\binom{k}{N}\tag{*}$$

of being within the first pile, for then the chance of this sample actually being drawn by the first player would be

$$\Pr(P) = \Pr(P\,|\, P \subset P_1)\Pr(P\subset P_1) = \frac{1}{\binom{k}{n}}\frac{\binom{k}{n}}{\binom{k}{N}} = \frac{1}{\binom{k}{n}},$$

as in case (1).

There are many ways to assure that $(*)$ holds for both players. For instance, this will occur whenever $P_1$ is a simple random sample of the $N$ pieces having at least $k$ pieces and no more than $N-m$ pieces (for otherwise Player 2 won't have enough pieces in his pile to draw from). You may choose the size of the pile in advance, using any arbitrary mechanism, or you could even choose it randomly. But once it has been chosen, you need to obtain a random sample of that size when making up the first pile. Because what's left over in pile $P_2$ is also a simple random sample, this works for the second player, too.


Comments

As an example of the subtleties that can arise in sampling situations like this, suppose that the pieces come in pairs, one red and one black. Make up the first pile $P_1$ by drawing a simple random sample of $n$ pieces--but observe the color of the first piece drawn. If it is black, substitute the corresponding black piece for every red piece in the pile. If it is red, substitute the corresponding red piece for every black piece in the pile. The remaining $N-n$ pieces make up pile $P_2$. This procedure has the following characteristics:

  1. It is random.

  2. Every piece has an equal chance of being in a given player's sample.

  3. Its results obviously differ from case (1), because now the first player always has either all black or all red pieces!

This is why it is important to perform analyses (like this one) that evaluate the probabilities of the possible samples rather than just the probabilities of the individual pieces. Such analyses are the basis of a rigorous theory of sampling and "observational economy" as described, for instance, by Steven K. Thompson.


Reference

Thompson, Steven. Sampling. J. Wiley & Sons (1992; Third Edition 2012).

$\endgroup$
0
$\begingroup$

If they draw until all tokens are taken then consider 2 cases:

First, they take turns drawing until all are gone (your case 1 above).

Second, they do the same as in 1st, then place their pile in front of them and again take turns drawing from their pile again. This is equivalent to your 2nd case above, but will result in the exact same final draws as the first case.

If they do not draw all the tokens, but just $x$ tiles (where $x < \frac{N}{2}$), then change the first above to doing the same thing, but then only keeping the first $x$ tokens for the 1st case and redrawing $x$ tokens in the second case.

So the 2 are the same in general.

You can also compute the exact probabilities:

Under the 1st case what is the probability that a particular token is taken by person 1? it is $\frac1N + \frac1{N-2}\frac{N-2}{N} + \frac1{N-4}\frac{N-4}N + \cdots + \frac1{N-2(x-1)}\frac{N-2(x-1)}N = \frac{x}N$ That is the probability of drawing it on the 1st draw plus the probability of drawing it on their 2nd draw (3rd draw total) give it was not already selected in a previous draw $\ldots$. The same calculations work for player 2 and also result in $\frac{x}{N}$.

For the 2nd case, for player 1 to have a chance of drawing a given token then it must first be in their pile, if the number of tokens in their pile is $y$ then that probability is $\frac{y}{N}$, but if it is then they are only drawing from $y$ possibilities instead of $N$, so you replace all the $N$'s above with $y$, but then multiply the whole thing by $\frac{y}{N}$ and it all works out to $\frac{x}{N}$.

So the probabilities are identical before any division/drawing is made (it also does not matter if player 1 takes all theirs first, then player 2 draws from the remaining, or some other ordering).

The only place you will see a difference is if you condition on the piles or the ordering within the piles, or something else that will not be known ahead of time if everything is truly random.

$\endgroup$
3
  • $\begingroup$ For the demonstration to be complete, it needs to show that every possible sample (not just any possible token) has the same probability in both scenarios. $\endgroup$
    – whuber
    Dec 29, 2015 at 21:49
  • $\begingroup$ @whuber, you are correct, but I left that as an exercise for the reader. It seems to me that it should be a straight forward (but possibly long) extension of what I did above. Do you have any evidence or intuition that the probabilities of every possible sample would differ? $\endgroup$
    – Greg Snow
    Dec 30, 2015 at 18:01
  • $\begingroup$ No, they won't differ, assuming certain things about the initial subdivision into piles (such as they have equal sizes!). But the point is that merely checking individual probabilities is not an adequate demonstration. $\endgroup$
    – whuber
    Dec 30, 2015 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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