01.5 Entropy and algorithms

The “20 Questions Problem”

Let $X$ be a random variable.

• What is the minimum amount of boolean questions needed to identify $X$?
• Which questions should be asked

• Consider a binary code $\Gamma$ for $X\in \mathcal{X}$
• Once $\Gamma$ is fixed, we know $x\in \mathcal{X}$ ⇐> we know the codeword $\Gamma (x)$
• We ask the $i$th question in order to obtain the $i$th bit
• The average number of questions is $L(X,\Gamma )$, which is minimized when $\Gamma$ is a Huffman code

→ The sequence of Yes/No answers is a binary codeword associated to $x$

Entropy and Sorting

Sorting with pairwise comparisons of two elements, with binary output → Either $<$ or $\ge$

But how many binary comparisons are needed ?

$$\mathbb{E}[\text{number of comparisons}]\ge H_2(X)$$ $$N\ge \max H_D(X)={\log }_3|\mathcal{X}|$$

Billiard Balls

We have 14 balls, and we have a ball as a reference (we know it’s normal). At most one ball can be heavier/lighter than the others.

How can find which ball is different ?

We can identify the solution with a random variable $X$

$$\begin{array}{lc}\text{all are heavy}& X=0\\ \text{Ball 1 heavy}& X=1\\ \text{Ball 1 light}& X=-1\\ \text{Ball 2 heavy}& X=2\\ \text{Ball 2 light}& X=-2\\ ⋮& ⋮\\ \text{Ball 13 heavy}& X=13\\ \text{Ball 13 light}& X=-13\end{array}$$

We have $X\in \mathcal{X}=\{-13,-12,\dots ,-1,0,1,\dots ,12,13\}$ Then the we have the size of the alphabet $|\mathcal{X}|=27$ Therefore the amount of ternary symbols needed to represent the source is at least

$$N\ge H_{D=3}(X)$$

Which we have the the amount of comparisons as

$$\max H_{D=3}(X)={\log }_3|X|={\log }_{3}27=3$$

Hence we need to do at least 3 comparisons (weighings)

⇒ Most algorithms can be deduced as a tree of decisions

01.6 Prediction, Learning and Cross-Entropy Loss