Homework Assignment 1

1. Problem 1: Intransitive dice

   Suppose you have 3 dice with the following numbers on their faces:

   Die	Faces
   A	6	3	3	3	3	3
   B	5	5	5	2	2	2
   C	4	4	4	4	4	1

   1. For each die, what is the average (expected) value per roll?
   2. Suppose you roll all three of these dice. One die defeats another if it rolls a higher value. Show that die A will defeat die B more than half the time. What about B vs C, and A vs C?

2. Problem 2: Likelihood ratio test

   Suppose I have an unfair coin with Pr[HEADS]=0.4. I also have a fair coin. You can't tell which is which.

   You choose one coin and flip it 20 times. Describe how you would use the outcomes to decide if it is fair.

   1. What is the likelihood ratio value for a single coin flip?
   2. What is the likelihood ratio value for "TTTHTHHHHTTTHHHTTTHT"?
   3. You are equally likely to choose the fair coin as the evil coin. Suppose all mistakes are equally costly, e.g. uniform costs. What threshold should you use?
   4. Suppose I hide the evil coin with 9 other fair coins. You choose one at random. Now what threshold should you use?

3. Problem 3: Breaking Vignère

   The cracking program on the course web page uses a function called test_using_LR() to perform a likelihood ratio test. There are two similar but unused functions in the code, called test_using_IC() and test_using_Entropy().

   The code is designed so you can swap these around, recompile the code and compare them. Give this a try.
   At the top of the source file, you will see:

   #define TEST_FUN test_using_LR

   You can change this one line and recompile.

   For this problem, choose a plain text of about 200 characters. Encrypt it with a short keyword, and run the cracking program on keyword lenghts 1 through 10. Now recompile the program to use the other test functions, and do the same. Provide your test results.

   Note that the other tests do not provide an estimate of the keyword. Only the likelihood ratio test does this.