Eine Informationsquelle sende die Buchstaben α1, . . . , αn mit den Wahrscheinlichkeiten p1, . . . , pn

Question

Ich weiß leider nicht wie ich das mit vollständiger Induktion lösen soll.

Answer 1

Versuchsmal mit dem Lagrangeansatz. Es muss diese Funktion maximiert werden
$$ H(p) = -\sum_{i=1}^n p_i \cdot \log_2(p_i)  $$
Damit sieht die Lagrangefunktion so aus:
$$ L(p,\lambda) = -\sum_{i=1}^n p_i \cdot \log_2(p_i)  + \lambda \left( \sum_{i=1}^n p_i - 1 \right)  $$
Es gilt dann
$$  (1) \quad L_{p_j} = -\sum_{i=1}^n \left[ \delta_{ij} \cdot \log_2(p_i) +p_i \cdot \delta_{ij} \cdot \frac{1}{p_i}  \right] + \lambda \cdot \delta_{ij} $$
also $$ (2) \quad -\left[ \log_2(p_j) + 1 \right] + \lambda = 0  $$ und
$$ (3) \quad  L_\lambda = \sum_{i=1}^n p_i - 1 = 0 $$
Aus (2) folgt $$ \lambda = \log_2(p_j) + 1 $$ also
$$ p_j = 2^{\lambda-1}  $$
Das in (3) eingesetzt ergibt $$ 1 = n \cdot 2^{\lambda-1} $$ oder $$ \lambda = 1+\log_2\left(\frac{1}{n}\right)  $$ das in (2) eingesetzt ergibt
$$ 1+\log_2\left(\frac{1}{n}\right) = \log_2(p_j) + 1  $$ also $$ p_j = \frac{1}{n} $$
Die Hessematrix ist
$$ L_{x_i x_j} = -\delta_{jk} \frac{1}{p_j} = -\frac{1}{p_k} < 0 $$ für \( i \ne j \), also liegt ein Maximum bei \( p_i = \frac{1}{n} \)vor. Es gilt also
$$  H(p) \le f\left( \frac{1}{n} \right) =-\sum_{i=1}^n \frac{1}{n} \cdot \log_2 \left(\frac{1}{n} \right) = -\log_2 \left(\frac{1}{n} \right) = \log_2(n) $$

Comments

Wir hatten die Hessematrix leider noch nicht gehabt. Gibt es noch eine andere Möglichkeit das zu lösen?

---

Nochmal ohne Induktion

Es gilt erstens

$$ -\sum_{j=1}^n p_j \log(p_j) = \sum_{j=1}^n p_j \log\left( \frac{1}{p_j} \right) \\\le -\sum_{j=1}^n p_j \log{q_j} = \sum_{j=1}^n p_j \log\left( \frac{1}{q_j} \right) $$
falls \( \sum_{j=1}^n q_j \le 1 \) gilt.

Beweis:
$$ \sum_{j=1}^n p_j \log\left( \frac{1}{p_j} \right) - \sum_{j=1}^n p_j \log\left( \frac{1}{q_j} \right) =\sum_{j=1}^n p_j \log\left( \frac{q_j}{p_j} \right) \le \\\frac{1}{\ln(2)}  \sum_{j=1}^n p_j \left( \frac{q_j}{p_j} -1 \right) = \frac{1}{\ln(2)}  \left( \sum_{j=1}^n q_j - \sum_{j=1}^n p_j \right) \le 0 $$

wegen \( \ln(x) \le x -1 \) für \( x > 0 \)
Beweis über erste und zweite Ableitung von \( f(x) = \ln(x) - x +1 \)

Wähle jetzt \( q_j = \frac{1}{n} \) dann folgt
$$ \sum_{j=1}^n p_j \log(p_j) \le \sum_{j=1}^n p_j \log(n) = \log(n)  $$