4 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 foir 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 10, 1,21. Here, any of the three possibilities are equally returned. ) RANDOM(k) returns an integer chosen uniformly at random from k to 2 (inclusive). Here, values less than are not returned. 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, Z,Y-0 PrIZ, X, Y)-0 Pr(IZ, Y. X]} = 0 Note: Drawing the probability trees in TEX probably using TikZ, while looking amazing, will suck your time. I would recommend hand-drawing, scanning and then embedding the image 4 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 foir 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 10, 1,21. Here, any of the three possibilities are equally returned. ) RANDOM(k) returns an integer chosen uniformly at random from k to 2 (inclusive). Here, values less than are not returned. 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, Z,Y-0 PrIZ, X, Y)-0 Pr(IZ, Y. X]} = 0 Note: Drawing the probability trees in TEX probably using TikZ, while looking amazing, will suck your time. I would recommend hand-drawing, scanning and then embedding the image