Landausymbole / oh notation

[FORYOUITERRA]

Advertising

ich hab hier nen klitzekleines problem:
angenommen, ich weiß, daß für eine folge X_n=O(n^a) mit a>0 und X_n>0 gilt, kann ich dann daraus folgern, daß (X_n)^{-1} = O(n^{-a})?

was ich nur gefunden habe ist, daß man i.A. (X_n)^{-1} = Omega(n^{-2}) ist.
falls die aussage nicht gilt, kann/muss ich also eine annahme für die konvergenzgeschwindigkeit von (X_n)^{-1} treffen?

[Brusko651]

Zitat von FORYOUITERRA ich hab hier nen klitzekleines problem: angenommen, ich weiß, daß für eine folge X_n=O(n^a) mit a>0 und X_n>0 gilt, kann ich dann daraus folgern, daß (X_n)^{-1} = O(n^{-a})?

nope, man findet eh leicht ein gegenbeispiel:

1/n ist ein O(n^3)
(weil das groß O bedeutet ja nur dass es HÖCHSTENS so schnell wächst, es kann aber auch um einiges langsamer wachsen natürlich. bzw es ist eben die Ungleichung |1/n| < M |n^3| erfüllt, z.B. für M=1.)

Aber (1/n)^(-1) = n ist kein O(1/n^3).

[FORYOUITERRA]

üblicherweise wählt man bei meinen anwendungen die konvergenzgeschwindigkeit kleinstmöglich so, daß es mitderselben geschwindigkeit wächst.
also
1/n =O(n^(-1)) (= Theta(n^(-1))

gilt es dann?

[Brusko651]

Kann man dann trotzdem nicht unbedingt so allgemein sagen. Du könntest als extremes Beispiel zum Beispiel die Folge haben:
x_n= 1/n für n ungerade
x_n= n^3 für n gerade
also
1, 8, 1/3, 64, 1/5, 216....

Dann hättest du auch
x_n = O(n^3)
und kannst den Exponenten nicht kleiner wählen als 3,
aber die Folge 1/x_n ist gleich n für ungerade n. Ist also unbeschränkt und divergent und sicher kein O(1/n^3).

[Brusko651]

Aber das war jetzt vielleicht nicht sehr hilfreich, deswegen versuch ich nochmal hilfreicher zu antworten.
f= O(g) bedeutet ja im Grunde genommen dass

f/g beschränkt ist.

Du willst im Grunde genommen also wissen, ob dann auch (1/f)/(1/g) = g/f beschränkt ist. Das kann man so im Allgemeinen eben nicht sagen, weil f/g ja gegen 0 laufen könnte und dann geht g/f gegen unendlich.
Aber wenn |f/g| irgendeine untere Schranke größer als 0 hat, dann könnte man durchaus sagen, dass |g/f| nach oben beschränkt ist, also dass g/f beschränkt ist und somit 1/f = O(1/g)

Insbesondere also zB wenn f/g -> 1 konvergiert, also wenn sie wirklich 'gleich schnell wachsen'.

edit:
übrigens ist natürlich wenn f/g -> 1
automatisch auch g/f -> 1.
Man schreibt dafür auch f~g. Vielleicht ist das in deiner Situation ein sinnvollerer Begriff um das Wachstum von FUnktionen zu vergleichen. Der Preis ist natürlich dass es ein weniger allgemeiner Begriff ist als das O. Also f/g->1 ist natürlich eine viel stärkere Bedingung als 'f/g ist beschränkt' und wird dementsprechend nur von weniger Funktionen erfüllt. (bzw. Folgen)

---

Geändert von Brusko651 (12. Juli 2012 um 21:56 Uhr)

[FORYOUITERRA]

mit anderen worten also, man kann nichts konkretes über das verhalten von (X_n)^(-1) aussagen, es sei denn die folgen sind proportional zueinander.
X_n/n^a konvergiert halt in meinem fall gegen eine konstante.

danke für die hilfe

[mfb]

Man kann keine obere Abschätzung für (X_n)^(-1) abgeben (wie denn auch, wenn man für X_n nur eine obere Schranke hat), wohl aber eine untere: Es ist nach unten durch Omega(n^{-a}) beschränkt.

X_n/n^a konvergiert halt in meinem fall gegen eine konstante.

Wenn du diese Konvergenz kennst und die Konstante nicht 0 ist, dann ist (X_n)^{-1} in O(n^{-a}).

[FORYOUITERRA]

nochmal das problem konkreter aufgreifen.

X_n = O(1) und X_n > 0 dann gilt 1/X_n = O(1).
Da:
X_n ist nach unten beschränkt, setze b=inf(X_n) dann gilt
0<b<=X_n<=c
somit also 1/X_n <=1/b =: b*
also 1/X_n=O(1).

daraus folgt dann unmittelbar:
n^a X_n = O(n^a)
und ((n^aX_n)^(-1) = O(n^(-a)).

d.h. unter der zusatzbedingung, daß die folgeglieder positiv sind, gilt es.

edit: mein ursprungsproblem war übrigens marginal komplizierter und ging über stochastische landau symbole. für die, die irgendwann selbst mal vor dem problem stehen:
X_n konvergiert in verteilung gegen X wobei X sowie X_n fast sicher positive zufallsvariablen sind. Dann ist (1/X_n) beschränkt in WS.

proof:
Wähle e>0, dann existiert ein M>0 so daß P(|X|<= M) < e. Das heißt mit WS 1 also P(|1/X| >= 1/M) < e.
Aufgrund der konvergenz in Verteilung ist nun jedoch für n>=N
|P(|X_n| <= M) |- e< |P(|X_n| <= M)-P(|X|<= M)| < e,
also
P(|X_n| <= M) =P(1/|X_n| >=1/ M) <2e.
da die menge n<N endlich ist, kann der wert von M, falls notwendig, noch angehoben werden, so daß die aussage für alle n gilt.

proof2: geht sogar noch einfacher. die funktion f(x) = 1/x ist für alle x!= 0 stetig.
da mit WS 1 P(X>0) gilt mit hilfe des continuous mapping theorems:
f(X_n) konvergiert in verteilung gegen f(X).
somit ist f(X_n)=O_p(1). fertig.

---

Geändert von FORYOUITERRA (13. Juli 2012 um 14:59 Uhr)

[sesslor]

Zitat von FORYOUITERRA nochmal das problem konkreter aufgreifen. X_n = O(1) und X_n > 0 dann gilt 1/X_n = O(1). Da: X_n ist nach unten beschränkt, setze b=inf(X_n) dann gilt 0<b<=X_n<=c somit also 1/X_n <=1/b =: b* also 1/X_n=O(1).

Aber was ist wenn inf(X_n) = 0? Ich vermute jetzt mal das das der Limes sein soll. Oder willst du das von vornherein ausschließen?

Den Rest hab ich nicht verstanden.

[FORYOUITERRA]

Zitat von sesslor Aber was ist wenn inf(X_n) = 0? Ich vermute jetzt mal das das der Limes sein soll. Oder willst du das von vornherein ausschließen? Den Rest hab ich nicht verstanden.

sorry, sollte in meinem fall direkt ausgeschlossen sein (X_n ist bei mir die summe von quadrierten termen, die ungleich null sind) -auf die nicht so feine art implizit direkt verwendet.

...man beachte übrigens, daß ich O(1) niht gebraucht habe, sondern die folge nur hinreichend weit weg von 0 sein muss.

---

Geändert von FORYOUITERRA (15. Juli 2012 um 00:26 Uhr)