\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath, amsthm,amssymb}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}
\newcommand\typel{\left[\left[}
\newcommand\typer{\right]\right]}
\newcommand\types[1]{\left[\left[#1\right]\right]}
\newcommand\setl{\left\{}
\newcommand\setr{\right\}}
\newcommand\email[1]{\begin{normalsize}\texttt{#1}\end{normalsize} }
\lstset{ %
language=Lisp, % choose the language of the code
basicstyle=\footnotesize, % the size of the fonts that are used for the code
numbers=left, % where to put the line-numbers
numberstyle=\footnotesize, % the size of the fonts that are used for the line-numbers
stepnumber=1, % the step between two line-numbers. If it's 1 each line will be numbered
numbersep=5pt, % how far the line-numbers are from the code
backgroundcolor=\color{white}, % choose the background color. You must add \usepackage{color}
showspaces=false, % show spaces adding particular underscores
showstringspaces=false, % underline spaces within strings
showtabs=false, % show tabs within strings adding particular underscores
frame=single, % adds a frame around the code
tabsize=2, % sets default tabsize to 2 spaces
captionpos=t, % sets the caption-position to bottom
breaklines=true, % sets automatic line breaking
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
%title=\lstname, % show the filename of files included with \lstinputlisting; also try caption instead of title
%escapeinside={\%*}{*)} % if you want to add a comment within your code
%morekeywords={*,...} % if you want to add more keywords to the set
}
%The last lines needs an explanation. You need it if you want to add some text within the code that will not be printed. Note that, by default, comments of the language you are inserting will be printed; the command escapeinside={A}{B} will define comments for listings only. All the code between the string "A" and "B" will be ignored. In the example above, the comments for Octave start with %, and they are going to be printed in the document unless they start with %*, but you have to remember to "close" the comment with another "*".
\begin{document}
\title{Cryptography: Handin \#2}
\author{S\o ren L\o bner\\ \email{lobner@cs.au.dk} }
\maketitle
\vspace*{1cm}
\subsection*{Handin 2}
The assignment is about a theoretic instance of Wheel of Fortune where you have to guess which collection of letters are hidden behind a row of cards in front of you.
Each of the letters are chosen independently from a distribution [$p_0, p_1, \dots ,p_{25}$]. At each round you get to choose one letter, the cards with that letter behind is then turned. So you must choose the one which reveals the most information, on all the letters combined.
\subsubsection*{First question} If your guess is the letter $i$, how many bits of information will you learn on average from playing the game (as a function of $p_i$ and N)?\\
At each guess we either learn that the letter is at the position(s) or that it is not there at all. We can model this as the random variable \textbf{X} which is defined on the set $X=\{T,F\}$ for $true$, the letter is there at one or more positions or $false$, the letter is not there.
The distribution function for this is then defined as:
\[ Pr[T]=p_i \]
\[ Pr[F]=(1-p_i) \]
\\
\\
Then by the following equation we calculate the entropy for a random variable
\[
H(X)=\sum_{x\in X} (Pr[x]\times log_2{\frac{1}{Pr[x]}})
\]
This for $T$ and $F$ gives us:
\begin{equation}
H(X)=p_i \times log_2{\frac{1}{p_i}}+(1-p_i)\times log_2{\frac{1}{(1-p_i)}}
\end{equation}
Now from the above we have the result for each card, so for all cards we multiply by $N$ and get:
\begin{equation}
T(p_i,N)=N \times (p_i \times log_2{\frac{1}{p_i}}+(1-p_i)\times log_2{\frac{1}{(1-p_i)}})
\end{equation}
\subsubsection*{Second question}
What strategy does your result suggest for choosing your guess, given frequencies
[$p_{0},\dots,p_{25}$] as in English?\\
If we use the frequencies [$p_{0},\dots,p_{25}$] as in English and use (2) to calculate the average bits of
information for E which is the most frequent letter and Z which is one of the less frequent letters
in English, we get
\begin{equation*}
E:~~~
T(0.127,N)=N \times (0.127 \times log_2{\frac{1}{0.127}}+(1-0.127)\times log_2{\frac{1}{(1-0.127)}})
\end{equation*}
\begin{equation*}
Z:~~~
T(0.001,N)=N \times (0.001 \times log_2{\frac{1}{0.001}}+(1-0.001)\times log_2{\frac{1}{(1-0.001)}})
\end{equation*}
This suggests that choosing the most frequent letters gets you the most bits of information.
\subsubsection*{Third question}
based on this, does it make sense that players in real life choose the most frequent letter(s)?\\
Yes it makes sense since they get the most bits of information on average.
\subsubsection*{Fourth question}
Would this be a good strategy no matter what the frequencies were?\\
No, if the most frequent letter is too frequent, that is if a letter has $p_i$ close to 1, then you should not choose it, because the average bits of information decreases after $i$ peaks at $p = \frac{1}{2}$ .So you should choose the letters that has a frequency as close to $p = \frac{1}{2}$ to get the highest average bits of information.
\end{document}