# Does re-ordering a shuffled pile while drawing from it affect the randomness of the draw?

In the game "Settlers of Catan", there is a stack of fourteen tiles, four of which are "water", two "gold", and the other eight an arbitrary mixture of "sheep", "wheat", "ore", "brick", and "lumber".

I shuffled these tiles, and then placed the tiles to create one to four islands.

1. I pulled the top tile and placed it in the first spot.
2. Then I took the new top tile and placed it on the bottom of the pile.
3. Repeat until all tiles placed.

The other players argued that my moving the top tile after every draw affected the randomness of the placement -- of the water tiles specifically -- and created a unrandom setup. They thought the usual procedure of placing the top one into the first spot, then the next tile into the second slot, and so on, would be better.

It seemed to me that my procedure was completely random and would not affect the location of the four water tiles in any way, as I had no knowledge of their location in the stack.

How do I prove to my friends that I didn't affect the outcome of the tiles other than to be completely random?

-

## migrated from stackoverflow.comApr 9 '12 at 21:15

This question came from our site for professional and enthusiast programmers.

Assuming that (a) you're following your procedure consistently, and (b) the deck was properly shuffled to begin with, it doesn't make a difference.

What your move-to-back procedure achieves is nothing more or less than what you could achieve by drawing the tiles in the ordinary order but filling up the spots on the game board(?) in a different, but fixed order. You could figure out exactly what the different order would be by starting with a stack of cards numbered 1 to 14 (in that order!) and deal them onto the board using the move-to-back order. The exact sequence you'd find is not important, but it is important that the initial position of a tile in the deck completely determines where on the board it will end up -- no matter which of the ways to deal you use.

Now, the assumption that the deck is properly shuffled to begin means that each of the $14!$ ways the deck could have been arranged is equally likely (for simplicity we're assuming that there's some way to tell "identical" tiles apart, even though this difference may have no gameplay effect). This again means that each of the $14!$ ways the tiles can end up on the board are equally likely.

However, the move-to-back dealing achieves exactly the same thing! Each of the $14!$ possible ways the tiles can end up on the board corresponds to one and only one way the deck must have been arranged before the move-to-back dealing started. And since each of those were assumed to be equally likely, each resulting distribution is also equally likely.

You would need a more involved argument than this if you're accused on choosing on the fly how to continue your deal based on which tiles you have already placed. A more careful analysis would still vindicate you (because each tile you see will reduce the number of possible configurations of the rest of the deck in such a symmetric way that you cannot get any information-theoretic advantage from it), but it would be rather less accessible.

And if the tiles were imperfectly shuffled to begin with, your procedure probably cannot make it worse -- unless the imperfection of the initial shuffling was of a very specific sort, fine-tuned to be made worse by your procedure.

-
In general, is it true that any non-choice-based reordering (i.e., reordering without looking at the draw and deciding what to do based on its value) will preserve the randomness (or equal likelihood of any of the possible orderings) of the shuffle? (Excepting the special cases you mention in your last paragraph, of course.) Or is that a whole separate question? – Josh Caswell Apr 10 '12 at 17:57
Yes, that's the general principle. Of course, convincing one's co-players that the procedure one is using is in fact "non-choice-based" might be a greater obstacle than the underlying mathematics. And if the people one needs to convince are the sort who thinks that "random" means "actively avoiding obvious patterns in the deal" rather than "each outcome (pretty or not) is equally likely", then all bets are off. – Henning Makholm Apr 10 '12 at 18:18

Actually, they're right.

Suppose you have a list:

['a', 'b', 'a', 'b']


And you pull your swapping trick, you'd wind up with:

place 'a',
move 'b' to bottom,
place 'a',
move 'b' to bottom


Which is equivalent to:

['a', 'a', 'b', 'b']


Now, that's not to say that you're cheating. Just drastically affecting the order of the list. This process doesn't help you, just has the potential to completely undo all of your shuffling.

-
Using your example I beg to differ, but I see your point. <br/>['a', 'b', 'c', 'd', 'e', 'f']<br/> And we pull the swapping trick, you'd wind up with:<br/> place 'a',<br/> move 'b' to the bottom, <br/>place 'c', <br/>move "d' to the bottom, .... etc. <br/>Which ends up as:<br/> ['a','c','e','b','f','d']<br/> vs<br/> ['a','b','c','d','e','f']<br/> still a random set of letters. – Michael Cox Apr 9 '12 at 18:30
Yes, but that's what shuffling is for. No need to possibly undo it. – pcperini Apr 9 '12 at 18:33
I guess the reason I chose to do the place to the bottom thing, was because being hex tiles instead of cards a proper shuffle couldn't be completely done. So I figured this might aid in completing the shuffle. (btw: sorry I suck at formatting these posts) – Michael Cox Apr 9 '12 at 18:35
No worries. Though, this might be of use: GitHub Flavored Markdown – pcperini Apr 9 '12 at 18:42
Thanks, appreciate the healthy chit chat – Michael Cox Apr 9 '12 at 18:45