1
$\begingroup$

I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned".

Is shuffling the "free" set after assigning an employee meaningfully more random than just doing it before I start putting people into the "assigned" set? How can I come up with proof of this?

$\endgroup$
  • 6
    $\begingroup$ Do you shuffle cards after each one is dealed? $\endgroup$ – Anthony Pegram Dec 16 '15 at 19:23
  • 1
    $\begingroup$ Have you tried calculating the probability of selecting person A next in either scenario? (This comes down to a pure mathematics question, by the way.) $\endgroup$ – Raphael Dec 17 '15 at 8:47
  • $\begingroup$ @AnthonyPegram Some games do have rules like that! $\endgroup$ – Raphael Dec 17 '15 at 9:02
  • $\begingroup$ If this was going to be migrated then is should have gone to stats.stackexchange.com $\endgroup$ – paparazzo Dec 17 '15 at 16:20
  • $\begingroup$ @Frisbee Don't think so. There is no statistics here. While probability theory is ontopic on Cross Validated, I think Mathematics would have been a more reasonable alternative. But since it is about analysing an algorithm, it's fine here (even though the answer is a simple calculation). $\endgroup$ – Raphael Dec 18 '15 at 6:36
5
$\begingroup$

Say we have $n$ people. After shuffling the whole list (once), every person occupies every position with probability $1/n$.

Shuffling before each draw means every choice is uniformly random; that is, because the choices are now stochastically independent, being drawn as $i$th person has probability

$\qquad\displaystyle \frac{1}{n-i+1} \cdot \prod_{k=1}^{i-1} \Bigl(1-\frac{1}{n-k+1}\Bigr) \quad=\quad \frac{1}{n}$.

So no, shuffling repeatedly does not "add" any randomness -- whatever that would mean. It's uniform, i.e. "fair", to begin with, so what would "more random" mean?

The correct statement is: repeated shuffling does not change the distribution. Which means it is unnecessary, but also not harmful if it eases the mind of laymen participants.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Here is a proof by converse. If the second is not random then you have no proof the first is random.

A shuffle is only valid if every position is random. If every position is not random then the first position is not random.

Once you pop, the free person has been removed. The remaining is exactly the set of free.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A gentle reminder to use respectful language -- thank you! $\endgroup$ – D.W. Dec 17 '15 at 8:01
  • $\begingroup$ @EvilJS What? The size was X. Take one off the top and you have X-1. Person A now has X-1 chance of the being the (new) top card. Shuffle again and Person A still has a X-1 chance of being the top card. In a card game do you ask the players if they want reshuffle after every card is dealt? If have evidence the probability changes then post an answer. $\endgroup$ – paparazzo Dec 17 '15 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy