Ungleichung Beweisen



  • Ich bin gerade auf eine Ungleichung gestossen, die "der interessierte Leser als einfache Uebung beweisen kann". Es sollte eigentlich tatsaechlich nicht so schwierig sein aber ich stehe gerade auf dem Schaluch πŸ™„

    Sei XX eine Zufallsvariable ueber dem endlichen Alphabeth X\mathcal{X}. Wir definieren pmax(X):=maxx∈XPX(x)p_{max}(X) := \max\limits_{x \in \mathcal{X}}P_X(x) und pcoll(X):=βˆ‘x∈X(PX(x))2p_{coll}(X) := \sum\limits_{x \in \mathcal{X}} \left(P_X(x)\right)^2.

    Nun soll man zeigen, dass
    1/∣Xβˆ£β‰€pcoll(X)≀pmax(X)1/|\mathcal{X}| \leq p_{coll}(X) \leq p_{max}(X)
    gilt.

    Lustigerweise bin ich mir ziemlich sicher dass ich die Behauptung schon einmal beweisen habe (ich lese das ganze gerade zum zweiten Mal). Aber irgendwie komme ich nicht mehr drauf. Kann mir jemand den Beweis zeigen oder zumindest einen Hinweis geben wie man das sauber zeigt?



  • Welche der beiden Ungleichungen ist das Problem?



  • wx++ schrieb:

    Welche der beiden Ungleichungen ist das Problem?

    Beide πŸ˜ƒ



  • Ich habs nun herausgefunden wie es geht. Ist wirklich nicht allzu schwierig aber man braucht die richtige Idee.

    Die erste Ungleichung kann wie folgt gezeigt werden.
    pcoll(X)=βˆ‘x∈XP_X(x)2=∣Xβˆ£βˆ‘_x∈X1∣X∣P_X(x)2β‰₯∣X∣(βˆ‘_x∈X1∣X∣P_X(x))2=1∣X∣(βˆ‘_x∈XPX(x))2=1∣X∣,p_{coll}(X) = \sum\limits_{x \in \mathcal{X}} P\_X(x)^2 = |\mathcal{X}| \sum\limits\_{x\in\mathcal{X}} \frac{1}{|\mathcal{X}|} P\_X(x)^2 \geq |\mathcal{X}| \left(\sum\limits\_{x \in \mathcal{X}} \frac{1}{|\mathcal{X}|} P\_X(x)\right)^2 = \frac{1}{|\mathcal{X}|} \left(\sum\limits\_{x \in \mathcal{X}} P_X(x)\right)^2 = \frac{1}{|\mathcal{X}|},
    wobei wir in Schritt 3 Jensen's Ungleichung fuer konvexe Funktionen verwendet haben.

    Die zweite Ungleichung ergibt sich durch
    pcoll(X)=βˆ‘x∈XP_X(x)2β‰€βˆ‘_x∈XP_X(x)β‹…max_xβ€²βˆˆXP_X(xβ€²)=max_xβ€²βˆˆXP_X(xβ€²)βˆ‘_x∈XP_X(x)=p_max(X).p_{coll}(X) = \sum\limits_{x \in \mathcal{X}} P\_X(x)^2 \leq \sum\limits\_{x \in \mathcal{X}} P\_X(x) \cdot \max\limits\_{x' \in \mathcal{X}} P\_X(x') = \max\limits\_{x' \in \mathcal{X}} P\_X(x') \sum\limits\_{x \in \mathcal{X}} P\_X(x) = p\_{max}(X).



  • Gut dass ich nochmal neu geladen habe, bevor ich so viel Latex tippe πŸ˜ƒ



  • wx++ schrieb:

    Gut dass ich nochmal neu geladen habe, bevor ich so viel Latex tippe πŸ˜ƒ

    πŸ˜ƒ πŸ‘



  • Die erste Ungleichung erhΓ€ltst du auch mit Cauchy-Schwartz:
    pcoll(X)=1∣X∣(βˆ‘x∈XP_X(x)2)(βˆ‘_x∈X12)β‰₯1∣X∣(βˆ‘x∈XPX(x))2=1∣X∣p_{\text{coll}}(X) = \frac 1{\lvert\mathcal X\rvert} \left(\sum\limits_{x \in \mathcal{X}} P\_X(x)^2\right)\left(\sum\limits\_{x \in \mathcal{X}} 1^2\right) \geq \frac 1{\lvert\mathcal{X}\rvert}\left(\sum\limits_{x\in\mathcal{X}} P_X(x)\right)^2 = \frac 1{\lvert\mathcal{X}\rvert}



  • Schaluch schrieb:

    Die erste Ungleichung erhΓ€ltst du auch mit Cauchy-Schwartz:
    pcoll(X)=1∣X∣(βˆ‘x∈XP_X(x)2)(βˆ‘_x∈X12)β‰₯1∣X∣(βˆ‘x∈XPX(x))2=1∣X∣p_{\text{coll}}(X) = \frac 1{\lvert\mathcal X\rvert} \left(\sum\limits_{x \in \mathcal{X}} P\_X(x)^2\right)\left(\sum\limits\_{x \in \mathcal{X}} 1^2\right) \geq \frac 1{\lvert\mathcal{X}\rvert}\left(\sum\limits_{x\in\mathcal{X}} P_X(x)\right)^2 = \frac 1{\lvert\mathcal{X}\rvert}

    Jup, diese Variante ist eleganter als meine πŸ‘

    Danke.


Log in to reply