2
$\begingroup$

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.

I thought about this as a loop:
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?

2 Answers 2

1

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.

  • 1
    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.2012-04-10
-1

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.

  • 0
    Created an excel sheet that shows the random shuffle and the top to bottom from that random shuffle. Now just have to figure out if that proves my theory that both are equally random.2012-04-09