Min hverdag

Så blev jeg færdig med aflevering 2. Jeg må ærligt indrømme at den bestemt ikke er noget jeg er særlig stolt af. Føler ikke den blev særlig god. Anyways.. Here it is. Tak til Jakob Rosenlund for grafen, som han har lavet ved hjælp af et eller andet gnu-linux værk.

I denne uge handlede det om at vi skulle finde en strategi til hvordan vi får mest mulig information ud af streng som vi ikke kan se ved at gætte på forskellige bogstaver. Her spiller Entropy en central rolle.

Opgaveteksten er som følger (Taget direkte fra Kryptologi siden):

Suppose you get to play the following variant of the bonus round in the TV show

Wheel of Fortune (Lykkehjulet): you are shown N cards, each of which cover one letter.

Each letter has been independently chosen from the same distribution, and you are given

the distribution (p0, p1,…, p25). You get to choose one letter from the alphabet, say you choose

letter i. Now every position in the hidden string where letter i occurs (if any) are uncovered.

Your goal is to learn (on average) as much information as possible on the hidden string.

(Of course this is a very crude model of Wheel of Fortune since we only consider single letter

frequencies, but we want something that is feasible to analyze)

In the real-version of the game, people tend to choose the most frequent letter as their guesses. Let’s

try to see what information theory has to say about this. Suppose we adopt the convention that Shannon

used when defining Entropy: if you know that some event occurs with probability p, and you learn that

this event did indeed occur, you have learnt log(1/p) bits of information.

Now, if your guess is letter nr. i, how many bits of information will you learn on average from

playing the game (as a function of pi and N)? Hint: note that for every position in the hidden

string you learn either that letter i occurred here, or that it did not occur.

What strategy does your result suggest  for choosing your guess, given frequencies p0,..,p25

as in English? based on this, does it make sense that players in real life choose the most frequent

letter(s)? Would this be a good strategy no matter what the frequencies were?

Link til afleveringen finder du her: Kryptologi Aflevering 2

Related posts:

1. Kryptologi: Aflevering 1 done