matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenStatistik (Anwendungen)Ungleichung Ordnungsstatistik
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Statistik (Anwendungen)" - Ungleichung Ordnungsstatistik
Ungleichung Ordnungsstatistik < Statistik (Anwend.) < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Statistik (Anwendungen)"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ungleichung Ordnungsstatistik: Tipp bzw. Idee
Status: (Frage) überfällig Status 
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

        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ungleichung Ordnungsstatistik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!


Bezug
                        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
Datum: 19:17 Fr 14.08.2015
Autor: statler

Pardon, und siehe unten.

Bezug
        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ungleichung Ordnungsstatistik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                
Bezug
Ungleichung Ordnungsstatistik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!

Bezug
        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ungleichung Ordnungsstatistik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Ungleichung Ordnungsstatistik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                                
Bezug
Ungleichung Ordnungsstatistik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:06 Sa 15.08.2015
Autor: ito

okay, die Ungleichungen gelten in der Tat...
Jetzt verstehe ich es auch.
Dank dir!

Bezug
                                                
Bezug
Ungleichung Ordnungsstatistik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?


Bezug
                                                        
Bezug
Ungleichung Ordnungsstatistik: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                                                
Bezug
Ungleichung Ordnungsstatistik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:14 Sa 15.08.2015
Autor: ito

Hat sich erledigt.  Danke und schoenes WE!
Bezug
                                
Bezug
Ungleichung Ordnungsstatistik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:54 Fr 14.08.2015
Autor: tobit09

Hallo Dieter!


Schöner Ansatz. [ok] Tatsächlich scheint er zu funktionieren.


Viele Grüße
Tobias

Bezug
        
Bezug
Ungleichung Ordnungsstatistik: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:20 Mi 19.08.2015
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Statistik (Anwendungen)"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]