Entropie unter Gleichverteilung maximal

Neue Frage »

05.11.2021, 16:50	Malcang	Auf diesen Beitrag antworten »
Entropie unter Gleichverteilung maximal Hallo Leute, das Thema ist zwar aus der Kryptographie, aber die Anwendung ist analytisch. Hoffe daher, das richtige Forum erwischt zu haben Es sei $\begin{eqnarray} X \end{eqnarray}$ eine Zufallsvariable mit Wertemenge $\begin{eqnarray} \left\{ x_1,\dots,x_m\right\} \end{eqnarray}$ . Diese seien gleichverteilt, es gilt also $\begin{eqnarray} P(X=x_i) = \frac{1}{m}\forall 1\leq i\leq k \end{eqnarray}$ . Es sei $\begin{eqnarray} H_C(X) = -\sum\limits_{i=1}^{m}P(X=x_i)\cdot\log_c(P(X=x_i)) \end{eqnarray}$ die Entropie von X zur Basis $\begin{eqnarray} C>1 \end{eqnarray}$ . Nun soll gezeigt werden, dass genau für eine Gleichverteilung diese Entropie maximal wird. Im ersten Teil wurde zwar gezeigt, dass die Funktion $\begin{eqnarray} f(x) = -x\cdot\log(x) \end{eqnarray}$ konkav ist für alle reellen $\begin{eqnarray} x>0 \end{eqnarray}$ , aber ich weiß nicht, wie ich das hier nun einbringen kann. Mein Ansatz war zu sagen, dass oBdA $\begin{eqnarray} P(X=x_1) = \frac{1}{m}+\epsilon \end{eqnarray}$ und $\begin{eqnarray} P(X=x_2) = \frac{1}{m}-\epsilon \end{eqnarray}$ seien und die anderen $\begin{eqnarray} m-2 \end{eqnarray}$ Wahrscheinlichkeiten jeweils $\begin{eqnarray} \frac{1}{m} \end{eqnarray}$ , aber das war nicht zielführend. Wie kann ich das lösen? Ich komme hier nicht weiter.
05.11.2021, 17:41	HAL 9000	Auf diesen Beitrag antworten »
Sagt dir der Herr Jensen was?
05.11.2021, 17:46	Malcang	Auf diesen Beitrag antworten »
Hi HAL 9000, jetzt sagt mir der Name was Im Wiki-Artikel steht ja genau, was ich brauche. Wunderbar! In unserer Vorlesung kam das nicht vor, von daher wäre ich da nicht drauf gekommen. Allerdings geht die Aufgabe ja auch davon aus, dass die zweite Ableitung beziehungsweise deren Interpretation bekannt ist. Von daher werde ich hier sicherlich auf diese Ungleichung zurückgreifen dürfen. Vielen Dank für den Hinweis!
05.11.2021, 18:52	Malcang	Auf diesen Beitrag antworten »
Bitte um Entschuldigung, aber ich bekomme es leider doch nicht hin. Also die letzte Zeile des "Beweis von Jensen" im Wikiartikel ist ja [attach]53920[/attach]. Die $\begin{eqnarray} \lambda_i \end{eqnarray}$ kann ich in meinem Fall ja als Wahrscheinlichkeiten auffassen und diese addieren sich zu 1. Aber ich sehe gerade den korrekten Ansatz nicht bzw habe mich zu sehr in meinem Ansatz verlaufen, und aus sowas komme ich immer nur ganz schwer wieder raus. Könntest du mir da nochmal einen Tritt geben?
05.11.2021, 20:16	HAL 9000	Auf diesen Beitrag antworten »
Mit $\begin{eqnarray} \lambda_i = \frac{1}{m} \end{eqnarray}$ und $\begin{eqnarray} x_i = p_i \end{eqnarray}$ angewandt auf das konkave $\begin{eqnarray} f(x)=-x\log_c(x) \end{eqnarray}$ folgt $\begin{eqnarray} \sum_{i=1}^m \frac{1}{m} f(p_i) \leq f\left(\sum_{i=1}^m \frac{1}{m} p_i\right) = f\left(\frac{1}{m}\right) \end{eqnarray}$ $\begin{eqnarray} -\frac{1}{m} \sum_{i=1}^m p_i\log_c(p_i) \leq -\frac{1}{m}\log_c\left(\frac{1}{m}\right) = \frac{1}{m}\log_c(m) \end{eqnarray}$ $\begin{eqnarray} -\sum_{i=1}^m p_i\log_c(p_i) \leq \log_c(m) \end{eqnarray}$ .
05.11.2021, 21:44	Malcang	Auf diesen Beitrag antworten »
Vielen Dank nochmal HAL. Das werde ich morgen nochmal vernünftig aufschreiben. Für heute merke ich, ist die Luft raus. Werde mich aber damit auseinandersetzen und das hier nochmal anbringen. Vielen Dank, gute Nacht
Anzeige

06.11.2021, 18:07	Malcang	Auf diesen Beitrag antworten »
Hallo wieder, auf die Gefahr hin, dass ich mich jetzt komplett zum Affen mache: Ich weiß, dass für die Entropie $\begin{eqnarray} H_c(X) \end{eqnarray}$ gilt: $\begin{eqnarray} H_c(X) \leq \log_c(m) \end{eqnarray}$ , wobei $\begin{eqnarray} \left\{x_1,\dots,x_m\right\} \end{eqnarray}$ die Zielmenge der Zufallsvariablen X ist. Nun weiß ich, dass für $\begin{eqnarray} P(X=x_i) = \frac{1}{m} \end{eqnarray}$ dieses Maximum angenommen wird. Check. Aber nun muss ich noch folgern, dass dies nicht mehr gilt, falls ein $\begin{eqnarray} x_i \end{eqnarray}$ existiert mit $\begin{eqnarray} P(X=x_i) \neq\frac{1}{m} \end{eqnarray}$ . HAL, ich nehme an dass du mir genau das wahrscheinlich beantwortet hast, aber ich sehe da leider gerade keinen Ausweg. Was ich aus deinem Beitrag entnehme ist, dass hier die Obergrenze von $\begin{eqnarray} \log_c(m) \end{eqnarray}$ nochmal bekräftigt wird. Ich hätte nun eine scharfe Ungleichung erwartet unter der Prämisse, dass eben keine Gleichverteilung vorliegt. Entschuldige bitte vielmals wenn ich jetzt zum dritten Mal das gleiche frage
06.11.2021, 18:22	HAL 9000	Auf diesen Beitrag antworten »
Auf dem beschriebenen Weg geht das eigentlich nur, wenn man die strenge Variante der Jensenschen Ungleichung bemüht: Die erfordert dann allerdings auch eine streng konkave statt "nur konkaver" Funktion und besagt, dass sogar $\begin{eqnarray} < \end{eqnarray}$ statt nur $\begin{eqnarray} \leq \end{eqnarray}$ gilt, sobald $\begin{eqnarray} i,j \end{eqnarray}$ existieren mit $\begin{eqnarray} x_i\neq x_j \end{eqnarray}$ sowie $\begin{eqnarray} \lambda_i>0 \end{eqnarray}$ und $\begin{eqnarray} \lambda_j>0 \end{eqnarray}$ . Oder man lässt Jensen gleich ganz sein und argumentiert so: Angenommen, es gibt eine Nichtgleichverteilung mit maximaler Entropie. In dieser Verteilung existieren demnach $\begin{eqnarray} i,j \end{eqnarray}$ mit $\begin{eqnarray} p_i\neq p_j \end{eqnarray}$ . Dann folgt aus der strengen Konkavität von $\begin{eqnarray} f(x)=-x\log_c(x) \end{eqnarray}$ gemäß Definition dieser strengen Konkavität $\begin{eqnarray} \frac{1}{2}f(p_i) + \frac{1}{2}f(p_j) < f\left(\frac{p_i+p_j}{2}\right) \end{eqnarray}$ $\begin{eqnarray} f(p_i) + f(p_j) < 2\cdot f\left(\frac{p_i+p_j}{2}\right) \end{eqnarray}$ . Das bedeutet: Ersetzt man $\begin{eqnarray} p_i,p_j \end{eqnarray}$ in dieser Verteilung durch $\begin{eqnarray} p_i' = p_j' = \frac{p_i+p_j}{2} \end{eqnarray}$ und belässt alle anderen Wahrscheinlichkeiten bei ihren alten Werten, dann besitzt diese veränderte Verteilung eine höhere Entropie als die Ausgangsverteilung. Das steht im Widerspruch zur Annahme, dass die Ausgangsverteilung bereits die maximale Entropie hat!!!
06.11.2021, 18:27	Malcang	Auf diesen Beitrag antworten »
Ah, die zweite Erklärung leuchtet mir sofort ein. Mit der von dir genannten Ungleichung von Jensen werde ich mich im Nachgang trotzdem noch beschäftigen, gelöst und verstanden habe ich die Aufgabe allerdings nun. Ich danke dir vielmals und wünsche ein schönes Wochenende!

Neue Frage »

Antworten »

Entropie unter Gleichverteilung maximal

Verwandte Themen