Question

An on-line card game uses a deck of 32 cards containing 4 Aces, 8 Kings, 16 Queens, 2 Jacks and 2 Tens. In each round of the game the cards are shuffled, the players make a bet about what type of card will be drawn, then a single card is drawn and the winners are paid off. The drawn card is reinserted into the deck before the next round begins.

i. How much information does a player receive when she is told that a King has been drawn? Which type of card yields the least information? ii. What is the average information content received when learning about the outcome of a round (aka the entropy)? Show your work.

iii. Use Huffman’s algorithm to create a variable-length prefix-free encoding that minimizes the expected length of messages reporting the outcome of a sequence of rounds (show the steps in building the tree). Specify your encoding for each of Ace, King, Queen, Jack and Ten. What is the expected length of a message reporting the outcome of 1000 rounds iv. One day there is a strange outage that causes the Queens to be omitted from the deck. Is the entropy reduced or increased? What is now the expected length of a message reporting the outcome of 1000 rounds (conditional on the omission of all Queens)?

Answer 1