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)$$