Ungleichung Ordnungsstatistik < Statistik (Anwend.) < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:40 Di 11.08.2015 | | Autor: | ito |
| Aufgabe | Angenommen wir haben zwei Stichproben [mm] $x_1,\ldots, x_n$ [/mm] und [mm] $y_1, \ldots, y_n$ [/mm] mit
$$ [mm] \max_{i=1,\ldots,n}|x_i [/mm] - [mm] y_i| [/mm] = M.$$
Dann folgt für die Ordnungsstatistiken [mm] $x_{(1)}, \ldots, x_{(n)}$ [/mm] und [mm] $y_{(1)}, \ldots, y_{(n)}$ [/mm]
$$ [mm] \max_{i=1,\ldots,n}|x_{(i)} [/mm] - [mm] y_{(i)}| \le [/mm] M.$$
Ordnungsstatistik bedeutet, dass die Stichprobe [mm] $x_1,\ldots, x_n$ [/mm] aufsteigend geordnet wird, d.h. es gilt
$$ [mm] x_{(1)} \le \ldots \le x_{(n)}$$
[/mm]
sowie
[mm] $$x_{(1)}=\min_{i=1,\ldots,n} x_i$$
[/mm]
und
[mm] $$x_{(n)}=\max_{i=1,\ldots,n} x_i$$ [/mm] |
Anfangs dachte ich, dass die Aussage falsch ist, aber nach dem ich verschiedene Stichproben simuliert habe, bin ich anderer Meinung.
Nun würde ich gerne verstehen wieso die Aussage stimmt...
Klar kann man die $max$-Funktion vernachlässigen, wenn man variable in den Indizes bleibt.
Also
[mm] $$\max_{i=1,\ldots,n}|x_i [/mm] - [mm] y_i| \le [/mm] M [mm] \gdw |x_i [/mm] - [mm] y_i| \le [/mm] M, [mm] i=1;\ldots,n$$
[/mm]
Genauso fällt einem ja immer die Dreiecksungleichung ein, wenn man Beträge sieht. Aber ne zündende Idee hatte ich noch nicht...
Daher bräuchte ich Hilfe. Vielen Dank
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:41 Do 13.08.2015 | | Autor: | statler |
Hallo,
wo liegt denn in den Ordnungsstatistiken dasjenige y, das von einem bestimmten xk den maximalen Abstand hat. Oder wenn es mehrere solche y's gibt, wo liegt dann eines von ihnen?
Wenn du Beispiele gemacht hast, was grundsätzlich ein guter Gedanke ist, müßtest du das herausfinden können und daraus dann auch einen Beweis zusammenbauen können.
Wie liegen also die Elemente des Paares aus der ungeordneten Stichprobe, auf dem das Maximum angenommen wird, in der Ordnungsstichprobe?
Gruß aus HH
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:05 Fr 14.08.2015 | | Autor: | ito |
Hallo Dieter,
vielen Dank für deinen Tipp. Leider verstehe ich nicht worauf du hinaus willst... :(
Ich gebe mal ein einfaches Beispiel:
$$x=(84, 1, 22, 86, [mm] 62)^T, [/mm] \ \ \ y=(94, 45, 76, 63, [mm] 51)^T$$
[/mm]
[mm] $$x_{(\cdot)}=(1, [/mm] 22, 62, 84, [mm] 86)^T, [/mm] \ \ \ [mm] y_{(\cdot)}=(45, [/mm] 51, 63, ,76, [mm] 94)^T$$
[/mm]
das Maximim $M=54$ wird in der dritten Komponente angenommen.
> wo liegt denn in den Ordnungsstatistiken dasjenige y, das
> von einem bestimmten xk den maximalen Abstand hat.
hmm, hängt das nicht vom Vorzeichen ab? verstehe den Hinweis an dieser Stelle nicht. Schaue ich mir [mm] $x_{(3)}=62$ [/mm] mit Abstand [mm] $|x_{(3)} [/mm] - [mm] y_{(3)}|=|62-63|$ [/mm] an. In der Stichprobe wird [mm] $x_{(3)}=x_5$ [/mm] mit [mm] $y_5=51<63$ [/mm] verglichen...
> Wie liegen also die Elemente des Paares aus der
> ungeordneten Stichprobe, auf dem das Maximum angenommen
> wird, in der Ordnungsstichprobe?
also [mm] $x_3$ [/mm] rutsch auf [mm] $x_{(2)}$ [/mm] und [mm] $y_3$ [/mm] rutsch auf [mm] $y_{(4)}$, [/mm] und nun? Vllt. kannst du noch ein wenig deutlicher werden oder deine Idee an meinem Beispiel konkretisieren?
Vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:17 Fr 14.08.2015 | | Autor: | statler |
Pardon, und siehe unten.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:16 Do 13.08.2015 | | Autor: | tobit09 |
Hallo ito!
> Angenommen wir haben zwei Stichproben [mm]x_1,\ldots, x_n[/mm] und
> [mm]y_1, \ldots, y_n[/mm] mit
> [mm]\max_{i=1,\ldots,n}|x_i - y_i| = M.[/mm]
> Dann folgt für die
> Ordnungsstatistiken [mm]x_{(1)}, \ldots, x_{(n)}[/mm] und [mm]y_{(1)}, \ldots, y_{(n)}[/mm]
> [mm]\max_{i=1,\ldots,n}|x_{(i)} - y_{(i)}| \le M.[/mm]
Die Aufgabe, dies zu beweisen, gefällt mir: Sie sieht scheinbar harmlos aus, aber erst nach einigen Stunden Überlegungen habe ich eine Lösung gefunden.
Falls Dieter wirklich eine einfachere Lösung haben sollte, bin ich schon gespannt auf sie...
> Ordnungsstatistik bedeutet, dass die Stichprobe
> [mm]x_1,\ldots, x_n[/mm] aufsteigend geordnet wird, d.h. es gilt
> [mm]x_{(1)} \le \ldots \le x_{(n)}[/mm]
> sowie
> [mm]x_{(1)}=\min_{i=1,\ldots,n} x_i[/mm]
> und
> [mm]x_{(n)}=\max_{i=1,\ldots,n} x_i[/mm]
Allein mit diesen Eigenschaften der Ordnungsstatistik wird kein Beweis gelingen.
Eine weitere Eigenschaft der Ordnungsstatistik ist die Folgende:
Sei [mm] $(x_1,\ldots,x_n)$. [/mm] Dann existiert eine bijektive Abbildung [mm] $f\colon\{1,\ldots,n\}\to\{1,\ldots,n\}$ [/mm] mit
[mm] $x_{(i)}=x_{f(i)}$
[/mm]
für alle [mm] $i=1,\ldots,n$.
[/mm]
(Anschaulich: [mm] (x_{(1)},\ldots,x_{(n)}) [/mm] geht aus [mm] $(x_1,\ldots,x_n)$ [/mm] durch Permutation der Indizes bzw. Vertauschung der Reihenfolge hervor.)
> Klar kann man die [mm]max[/mm]-Funktion vernachlässigen, wenn man
> variable in den Indizes bleibt.
> Also
> [mm]\max_{i=1,\ldots,n}|x_i - y_i| \le M \gdw |x_i - y_i| \le M, i=1;\ldots,n[/mm]
Guter Ansatz!
Wir müssen also zu beliebig vorgegebenem [mm] $i\in\{1,\ldots,n\}$ [/mm] die Ungleichung [mm] $|x_{(i)}-y_{(i)}|\le [/mm] M$ zeigen, wobei wir [mm] $|x_j-y_j|\le [/mm] M$ für alle [mm] $j=1,\ldots,n$ [/mm] voraussetzen dürfen.
> Genauso fällt einem ja immer die Dreiecksungleichung ein,
> wenn man Beträge sieht.
Die liefert hier wohl leider zu grobe Abschätzungen.
Die Beträge lassen sich wie folgt eliminieren:
Für jede reelle Zahl $a$ gilt die Äquivalenz
[mm] $|a|\le M\quad\iff\quad a\le M\;\wedge\; -a\le [/mm] M$.
Es gelten also die Äquivalenzen
[mm] $|x_{(i)}-y_{(i)}|\le [/mm] M$ [mm] $\iff$ $x_{(i)}-y_{(i)}\le M\;\wedge\; y_{(i)}-x_{(i)}\le [/mm] M$
und für jedes [mm] $j=1,\ldots,n$
[/mm]
[mm] $|x_j-y_j|\le [/mm] M$ [mm] $\iff$ $x_j-y_j\le M\;\wedge\; y_j-x_j\le [/mm] M$.
Es genügt also zu zeigen:
1. Wenn [mm] $x_j-y_j\le [/mm] M$ für alle [mm] $j=1,\ldots,n$ [/mm] gilt, dann gilt auch [mm] $x_{(i)}-y_{(i)}\le [/mm] M$.
2. Wenn [mm] $y_j-x_j\le [/mm] M$ für alle [mm] $j=1,\ldots,n$ [/mm] gilt, dann gilt auch [mm] $y_{(i)}-x_{(i)}\le [/mm] M$.
Aus Symmetriegründen können wir uns auf 1. beschränken.
Zum Nachweis von 1. gelte also [mm] $x_j-y_j\le [/mm] M$ für alle [mm] $j=1,\ldots,n$.
[/mm]
Zu zeigen ist nun [mm] $x_{(i)}-y_{(i)}\le [/mm] M$.
Wir bringen obige "Permutations-Eigenschaft" der Ordnungsstatistik ins Spiel:
Es existieren also Bijektionen [mm] $f,g\colon\{1,\ldots,n\}\to\{1,\ldots,n\}$ [/mm] mit
[mm] $x_{(j)}=x_{f(j)}$ [/mm] und [mm] $y_{(j)}=y_{g(j)}$
[/mm]
für alle [mm] $j=1,\ldots,n$.
[/mm]
Nun fällt folgendes Lemma vom Himmel:
Lemma: Es existieren Indizes [mm] $k,l\in\{1,\ldots,n\}$ [/mm] mit [mm] $k\le i\le [/mm] l$ und $f(l)=g(k)$.
Bevor ich das Lemma beweise, hier sein Nutzen:
Wir wählen Indizes $k,l$ wie im Lemma.
Dann folgt unter Ausnutzung von [mm] $x_{(1)}\le\ldots\le x_{(n)}$ [/mm] und [mm] $y_{(1)}\le\ldots\le y_{(n)}$ [/mm] wie gewünscht:
[mm] $x_{(i)}-y_{(i)}\le x_{(l)}-y_{(k)}=x_{f(l)}-y_{g(k)}=x_{g(k)}-y_{g(k)}\le [/mm] M$.
Beweis des Lemmas:
Seien [mm] $A:=\{f(i),f(i+1),\ldots,f(n)\}$ [/mm] und [mm] $B:=\{g(1),g(2),\ldots,g(i)\}$.
[/mm]
Wenn wir ein [mm] $j\in A\cap [/mm] B$ finden, sind wir quasi fertig:
Denn dann gilt $j=f(l)$ für ein [mm] $l\in\{i,i+1,\ldots,n\}$ [/mm] und $j=g(k)$ für ein [mm] $k\in\{1,2,\ldots,i\}$ [/mm] und somit $f(l)=g(k)$.
Zum Beweis der Existenz eines [mm] $j\in A\cap [/mm] B$ nehmen wir widerspruchshalber an, es gäbe kein solches $j$, d.h. A und B wären disjunkt.
Dann wäre
[mm] $|A\cup [/mm] B|=|A|+|B|$.
Wegen der Injektivität von f und g gilt
[mm] $|A|=|\{i,i+1,\ldots,n\}|=n-(i-1)=n-i+1$
[/mm]
und
[mm] $|B|=|\{1,2,\ldots,i\}|=i$.
[/mm]
Zusammengenommen erhalten wir
[mm] $|A\cup [/mm] B|=(n-i+1)+i=n+1$.
Wegen [mm] $A\cup B\subseteq\{1,\ldots,n\}$ [/mm] gilt jedoch im Widerspruch dazu
[mm] $|A\cup B|\le|\{1,\ldots,n\}|=n$.
[/mm]
Soweit mein Beweis.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:21 Fr 14.08.2015 | | Autor: | ito |
Hallo Tobi,
danke für deinen Beiweis! Werde ich mir später in Ruhe anschauen...
vorab zur Fallunterscheidung
> Es genügt also zu zeigen:
>
> 1. Wenn [mm]x_j-y_j\le M[/mm] für alle [mm]j=1,\ldots,n[/mm] gilt, dann gilt
> auch [mm]x_{(i)}-y_{(i)}\le M[/mm].
>
> 2. Wenn [mm]y_j-x_j\le M[/mm] für alle [mm]j=1,\ldots,n[/mm] gilt, dann gilt
> auch [mm]y_{(i)}-x_{(i)}\le M[/mm].
Wieso sollte denn für alle $j$ entweder [mm] $x_j-y_j\le [/mm] M$ oder [mm] y_j-x_j\le [/mm] M gelten?
Und dann behaupte ich mal wird die Abschätzung
> [mm]x_{(i)}-y_{(i)}\le x_{(l)}-y_{(k)}[/mm]
schwierig...
Hmm?! Ja, das problem sieht glaube ich wirklich einfacher aus als es ist :(
Viele Grüße
ito
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:22 Fr 14.08.2015 | | Autor: | tobit09 |
> vorab zur Fallunterscheidung
Hier war gar keine Fallunterscheidung gemeint.
> > Es genügt also zu zeigen:
> >
> > 1. Wenn [mm]x_j-y_j\le M[/mm] für alle [mm]j=1,\ldots,n[/mm] gilt, dann gilt
> > auch [mm]x_{(i)}-y_{(i)}\le M[/mm].
> >
> > 2. Wenn [mm]y_j-x_j\le M[/mm] für alle [mm]j=1,\ldots,n[/mm] gilt, dann gilt
> > auch [mm]y_{(i)}-x_{(i)}\le M[/mm].
>
> Wieso sollte denn für alle [mm]j[/mm] entweder [mm]x_j-y_j\le M[/mm] oder
> [mm]y_j-x_j\le[/mm] M gelten?
Wenn [mm] $|x_j-y_j|\le [/mm] M$ (für alle [mm] $j=1,\ldots,n$) [/mm] gilt (was wir voraussetzen), folgt sowohl
(*) [mm] $x_j-y_j\le|x_j-y_j|\le [/mm] M$
als auch
(**) [mm] $y_j-x_j\le|y_j-x_j|=|x_j-y_j|\le [/mm] M$.
Es genügt daher, anstelle der ursprünglichen Aussage 1. und 2. zu zeigen:
Aus 1. und (*) folgt dann [mm] $x_{(i)}-y_{(i)}\le [/mm] M$ und aus 2. und (**) folgt dann [mm] $y_{(i)}-x_{(i)}\le [/mm] M$.
> Und dann behaupte ich mal wird die Abschätzung
> > [mm]x_{(i)}-y_{(i)}\le x_{(l)}-y_{(k)}[/mm]
> schwierig...
Nein, die ist vergleichsweise einfach: Wegen [mm] $i\le [/mm] l$ gilt [mm] $x_{(i)}\le x_{(l)}$ [/mm] und wegen [mm] $i\ge [/mm] k$ ist [mm] $y_{(i)}\ge y_{(k)}$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:41 Sa 15.08.2015 | | Autor: | ito |
ahhhh, jetzt verstehe ich wieso es genügt, 1. und 2. zu zeigen...
klar dann ist die Abschätzung trivial.
dank dir tobi!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:14 Fr 14.08.2015 | | Autor: | fred97 |
Knackige Angelegenheit ....
Auch nach längerem Grübeln ist mir kein elementarer Beweis eingefallen. Schau hier mal rein:
http://people.clas.ufl.edu/avince/files/Rearrangement.pdf.
Sieh Dir das Theorem an und anschließend Example 4.
Sind nun $x=( [mm] x_1,\ldots, x_n) [/mm] $ und $ [mm] y=(y_1, \ldots, y_n) [/mm] $ Elemente des [mm] \IR^n [/mm] und setzt man
[mm] $\overline{x}:=(x_{(1)},...,x_{(n)}),
[/mm]
so bekommt man mit zweimaliger Anwendung von Example 4:
(*) [mm] ||\overline{x}-\overline{y}||_p \le ||x-y||_p,
[/mm]
dabei ist [mm] ||*||_p [/mm] die übliche p-Norm auf [mm] \IR^n [/mm] (p [mm] \ge [/mm] 1).
Bekannt sollte sein: [mm] \limes_{p\rightarrow\infty}||z||_p=||z||_{\infty} [/mm] für $z [mm] \in \IR^n$.
[/mm]
Damit folgt aus (*):
[mm] ||\overline{x}-\overline{y}||_{\infty} \le ||x-y||_{\infty}.
[/mm]
Gruß FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:56 Fr 14.08.2015 | | Autor: | ito |
An Permutationen hatte ich auch schon gedacht, da ich diese als Bijektion auf einer endlichen Menge kennen gelernt habe, habe ich den Gedanken nicht weiter verfolgt. Was passiert denn wenn die stichprobengröße $n$ gegen unendlich geht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:16 Fr 14.08.2015 | | Autor: | statler |
Hi,
bei meinem Anlauf oben bin ich wirklich über dünnes Eis gegangen, den ziehe ich mal zurück.
Aber: Man kann oEdA in der Stichprobe die Paare nach der Größe der [mm] x_{i} [/mm] ordnen. Wenn wir das getan haben, gucken wir uns die Fehlstellen bei den [mm] y_{i} [/mm] an. Also Paare (i, k) mit i < k und [mm] y_{i} [/mm] > [mm] y_{k}. [/mm] Was passiert mit der Anzahl der Fehlstellen, wenn ich diese beiden y's miteinander tausche? Und was passiert mit den Abständen?
Leider kann ich hier und jetzt kein Bild einscannen, aber die Anzahl der Fehlstellen wird kleiner und die beiden neuen Abstände sind jedenfalls [mm] \le [/mm] M. Und so kann man (hoffentlich) die Fehlstellen abarbeiten, bis auch die y's sortiert sind.
Ich hoffe, daß dieser Ansatz durchgeht.
Gruß aus HH
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:10 Fr 14.08.2015 | | Autor: | ito |
Hallo,
danke für die Hilfe!
Die Idee klingt gut, aber wieso sind die Abstände nach dem Tauschen (bei Fehlstand) kleiner M?
Kleiner werden die Abstände nach dem Tauschen nicht zwingend...
Wie schätzt du das ab?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:48 Sa 15.08.2015 | | Autor: | statler |
Hi ito,
> Kleiner werden die Abstände nach dem Tauschen nicht
> zwingend...
Das stimmt, macht aber nix.
> Wie schätzt du das ab?
Es gelten die folgenden Ungleichungsketten:
[mm] y_{i} [/mm] - M [mm] \le x_{i} \le x_{k} \le y_{i} [/mm] + M
und
[mm] x_{i} [/mm] - M [mm] \le y_{k} [/mm] < [mm] y_{i} \le x_{i} [/mm] + M,
wie man aus einer geeigneten Zeichnung schlagartig erkennt. Was man sich aber auch Schritt für Schritt zurechtlegen kann.
Gruß Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:06 Sa 15.08.2015 | | Autor: | ito |
okay, die Ungleichungen gelten in der Tat...
Jetzt verstehe ich es auch.
Dank dir!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:15 Sa 15.08.2015 | | Autor: | ito |
vllt. noch abschließend eine Frage:
Funktioniert die Vorgehensweise auch für goße $n$?
Also kann ich die Abschätzung benutzen um Konsistenz zu zeigen?
oder stellt sich da noch die Frage, ob die Fehlstände nach endlich vielen Schritten abgearbeitet werden?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:02 Sa 15.08.2015 | | Autor: | statler |
Hi!
> vllt. noch abschließend eine Frage:
> Funktioniert die Vorgehensweise auch für große [mm]n[/mm]?
Jetzt bin ich etwas übergerascht. n ist auf jeden Fall eine endliche Zahl, und die Anzahl der Fehlstände ist maximal [mm] \bruch{1}{2} \cdot [/mm] n [mm] \cdot [/mm] (n-1), also auch endlich. Bei jedem Austausch wird die Anzahl der Fehlstände echt kleiner, also kommt das Verfahren in endlicher Zeit zu einem Ende!
> Also kann ich die Abschätzung benutzen um Konsistenz zu
> zeigen?
Was ist hier 'Konsistenz'?
> oder stellt sich da noch die Frage, ob die Fehlstände
> nach endlich vielen Schritten abgearbeitet werden?
s. o.
Gruß aus HH
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:14 Sa 15.08.2015 | | Autor: | ito |
Hat sich erledigt. Danke und schoenes WE!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:54 Fr 14.08.2015 | | Autor: | tobit09 |
Hallo Dieter!
Schöner Ansatz. ![[ok]](/images/smileys/ok.gif "[ok]") Tatsächlich scheint er zu funktionieren.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Mi 19.08.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
