Question

CRYPTOGRAPHY PROBABILITY DISTRIBUTION
Bad Shuffles

Consider the following card shuffling algorithm. There are three cards in the deck and they are
each represented by an element in {X, Y, Z}. [Bonus marks if you use the deck {W, X, Y, Z}]
Algorithm Shuffle
---------------------------------------------------
deck := [X,Y,Z]
for i from 0 to 2 do
j := RANDOM(i)
swap values of deck[i] and deck[j]
end for
return deck
---------------------------------------------------
For each of the following definitions of RANDOM(i), compute the probability distribution of all six
valid hands, [X, Y, Z], [X, Z, Y ], [Z, X, Y ], etc., at the end of the algorithm. Show your work.
a) RANDOM(k) returns an integer chosen uniformly at random from the set {0, 1, 2}. Here, any
of the three possibilities are equally returned.
b) RANDOM(k) returns an integer chosen uniformly at random from k to 2 (inclusive). Here,
values less than k are not returned.
c) RANDOM(k) returns an integer chosen uniformly at random from the set {0, 1, 2} \ {k}. Here,
the value of k is never returned.
Your answer should give the probability of each possible hand. Briefly comment about the results
of the three algorithms.
Hint: Draw a tree starting with the un-shuffled deck [X, Y, Z] where the different outputs of the
RANDOM function yield a child (modified deck). The leaves are the tree are possible hands. The
probability of a leaf node (specific hand) is the product of the probabilities of the nodes on the
path from the root to that leaf.
Example: Suppose we use the functon RANDOM(k) -> k. The probability distribution is given by
Pr{[X, Y, Z]} = 1
Pr{[X, Z, Y ]} = 0
Pr{[Y, X, Z]} = 0
Pr{[Y, Z, X]} = 0
Pr{[Z, X, Y ]} = 0
Pr{[Z, Y, X]} = 0

Answer 1

a) Here probability of j=0 is 1/3, j=1 is 1/3, j=2 is 1/3

for [X,Y,Z]:

i should be equal to j.

so for i=0, j should be 0 (prob = 1/3)

for i=1, j should be 1 (prob=1/3)

for i=2, j should be 2 (prob=1/3)

Hence probability is 1/27.

similarly probabilities of all 6 combinations is 1/27.

b) if i=0, j=0,1,2

if i=1, j=1,2

if i=2, j=2

P[X,Y,Z] = (1/3)*(1/2)*(1) = 1/6

P[X,Z,Y] = (1/3)*(1/2)* 0 =0

Similarly, P[Z,Y,X]=0

P[Z,X,Y]=0

P[Y,Z,X]= 0

P[Y,X,Z] = (1/3)*(0)* 1 = 0

c) if i=0, j=1,2

if i=1, j=0,2

if i=2, j=0,1

P[X,Y,Z] = 0

And probability of all other cominations is (1/2)*(1/2)*(1/2) = 1/8