4. Ungleichung Beweisen

Ungleichung Beweisen

  • I

    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?

    0
  • W

    Welche der beiden Ungleichungen ist das Problem?

    0
  • I

    wx++ schrieb:

    Welche der beiden Ungleichungen ist das Problem?

    Beide 😃

    0
  • I

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

    0
  • W

    Gut dass ich nochmal neu geladen habe, bevor ich so viel Latex tippe 😃

    0
  • I

    wx++ schrieb:

    Gut dass ich nochmal neu geladen habe, bevor ich so viel Latex tippe 😃

    😃 👍

    0
  • ?

    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}

    0
  • I

    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.

    0
Anmelden zum Antworten