Rechnen mit Landau-Symbolen

26.01.2018, 14:32

blublablib

Rechnen mit Landau-Symbolen

Meine Frage:
Hallo zusammen,

ich habe folgende Gleichung vor mir
$\begin{eqnarray*} (1-\frac{k-1}{n-k})^k=1+O(\frac{k^2}{n}) \end{eqnarray*}$ .

Doch wie kommt man darauf?

Meine Ideen:
Meine Überlegung dazu ist bisher, dass nach Ausmultiplizieren nur die 1 fest bleibt und die restlichen Summmanden müssen sich ja dann nach Aussage der Gleichung wie $\begin{eqnarray*} \frac{k^2}{n} \end{eqnarray*}$ verhalten. Aber warum?

Vielen Dank schon mal für Eure Hilfe?

26.01.2018, 14:40

HAL 9000

Auf diesen Beitrag antworten »

Beim Rechnen mit Landausymbolen muss man eigentlich immer dazu sagen, um welchen Grenzübergang es dabei eigentlich geht. Meist geht das aus dem Zusammenhang/Kontext hervor - bei dir hier gibt es den nicht bzw. du hast ihn nicht dargestellt. Ich kann nur raten, dass es hier um $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ geht? Oder doch eher was mit $\begin{eqnarray*} k \end{eqnarray*}$ ? Du bist in der Lieferpflicht.

26.01.2018, 15:01

blublablib

Auf diesen Beitrag antworten »

Sorry, das hab ich vergessen anzugeben.

Du hast richtig geraten und es geht $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ , wobei $\begin{eqnarray*} 1\leq k\leq log_2(n) \end{eqnarray*}$ gilt.

26.01.2018, 15:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von blublablib
wobei $\begin{eqnarray*} 1\leq k\leq log_2(n) \end{eqnarray*}$ gilt.

Da bin ich etwas überfragt, wie ein solcher "doppelter" Grenzübergang $\begin{eqnarray*} n,k \end{eqnarray*}$ hinsichtlich Landau nun zu verstehen bzw. überhaupt definiert ist. verwirrt

Wenn es nur um $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ geht und $\begin{eqnarray*} k \end{eqnarray*}$ konstant bleibt, dann kann man genausogut auch $\begin{eqnarray*} 1+O\left(\frac{1}{n}\right) \end{eqnarray*}$ statt $\begin{eqnarray*} 1+O\left(\frac{k^2}{n}\right) \end{eqnarray*}$ schreiben, ist gehupft wie gesprungen. Allerdings gilt beim genauerer Analyse dort

$\begin{eqnarray*} \left(1-\frac{k-1}{n-k}\right)^k = 1-\frac{k(k-1)}{n} + O\left(\frac{1}{n^2}\right) \end{eqnarray*}$ ,

das ist aber dennoch nicht ausreichend für das, was dir wohl vorschwebt. verwirrt

26.01.2018, 15:30

blublablib

Auf diesen Beitrag antworten »

Ok, dann gehen wir mal davon aus, dass $\begin{eqnarray*} k \end{eqnarray*}$ fest gewählt ist. Wie kommst Du damit auf diesen Schritt?

Zitat:

Original von HAL 9000

$\begin{eqnarray*} \left(1-\frac{k-1}{n-k}\right)^k = 1-\frac{k(k-1)}{n} + O\left(\frac{1}{n^2}\right) \end{eqnarray*}$

Was passiert mit dem $\begin{eqnarray*} k \end{eqnarray*}$ aus dem Nenner?
Und verstehe ich das richtig, dass es egal ist, ob man $\begin{eqnarray*} 1+\mathcal{O}\left(\frac{1}{n}\right) \end{eqnarray*}$ oder $\begin{eqnarray*} 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ , eben weil $\begin{eqnarray*} k \end{eqnarray*}$ fest ist und für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ der Wert von $\begin{eqnarray*} k \end{eqnarray*}$ vernächlässigt werden kann?

26.01.2018, 15:49

IfindU

Auf diesen Beitrag antworten »

RE: Rechnen mit Landau-Symbolen
Übersehe ich hier was, oder ist $\begin{eqnarray*} 1 - \frac { k-1}{n-k} \in (0,1) \end{eqnarray*}$ und damit $\begin{eqnarray*} \left(1 - \frac { k-1}{n-k}\right)^k \leq 1 \end{eqnarray*}$ ?

26.01.2018, 16:03

HAL 9000

Auf diesen Beitrag antworten »

@IfindU

Das siehst du richtig - spricht ja nichts dagegen, dass es $\begin{eqnarray*} \leq 1 \end{eqnarray*}$ ist.

Zitat:

Original von blublablib
eben weil $\begin{eqnarray*} k \end{eqnarray*}$ fest ist

Ich hab davon geredet wenn (!) $\begin{eqnarray*} k \end{eqnarray*}$ fest ist. Leider weiß ich nicht, wie du das mit dem $\begin{eqnarray*} 1\leq k\leq \log_2(n) \end{eqnarray*}$ hinsichtlich $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ meinst, d.h., ob du eine Art "gleichmäßiges" Landau meinst - wie auch immer das definiert sein möge. Vielleicht soll

Zitat:

$\begin{eqnarray*} \left(1-\frac{k-1}{n-k}\right)^k = 1+O\left(\frac{k^2}{n}\right) \end{eqnarray*}$ für $\begin{eqnarray*} 1\leq k\leq \log_2(n) \end{eqnarray*}$ und $\begin{eqnarray*} n\to\infty \end{eqnarray*}$

ja folgendes bedeuten: Es existiert ein $\begin{eqnarray*} C>0 \end{eqnarray*}$ sowie $\begin{eqnarray*} n_0 \end{eqnarray*}$ mit

$\begin{eqnarray*} \sup\limits_{1\leq k\leq \log_2(n)} \frac{n}{k^2} \left|\left(1-\frac{k-1}{n-k}\right)^k-1\right| \leq C \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ .

26.01.2018, 16:11

IfindU

Auf diesen Beitrag antworten »

Deine Interpretation macht wohl mehr Sinn als meine. Ich dachte $\begin{eqnarray*} g(n,k) = 1 + O( f(n,k) ) \end{eqnarray*}$ , falls $\begin{eqnarray*} n_0\geq 0 \end{eqnarray*}$ und $\begin{eqnarray*} C \end{eqnarray*}$ existiert, so dass $\begin{eqnarray*} g(n,k) \leq 1 + C f(n,k) \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ und alle $\begin{eqnarray*} 1 \leq k \leq \log_2 n \end{eqnarray*}$ . Aber dann würde es ja trivial mit meiner Abschätzung folgen, da $\begin{eqnarray*} 1 = 1 + O(k^2/n) \end{eqnarray*}$ . Das ist wohl nicht gemeint.

26.01.2018, 16:20

HAL 9000

Auf diesen Beitrag antworten »

Die Behauptung gemäß meiner "Interpretation" kann man jedenfalls leicht beweisen: Für $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ gilt $\begin{eqnarray*} \log_2(n)\leq \frac{n}{2} \end{eqnarray*}$ , damit kann man für alle in Frage kommenden $\begin{eqnarray*} k \end{eqnarray*}$ grob abschätzen

$\begin{eqnarray*} 1- \left(1-\frac{k-1}{n-k}\right)^k \leq 1- \left(1-\frac{k-1}{n-\frac{n}{2}}\right)^k = 1-\left(1-\frac{2(k-1)}{n}\right)^k \stackrel{BU}{\leq} 1-\left(1-\frac{2k(k-1)}{n}\right) = \frac{2k(k-1)}{n} \end{eqnarray*}$

und damit

$\begin{eqnarray*} \sup\limits_{1\leq k\leq \log_2(n)} \frac{n}{k^2} \left|\left(1-\frac{k-1}{n-k}\right)^k-1\right| \leq \sup\limits_{1\leq k\leq \log_2(n)} \frac{2(k-1)}{k} \leq 2 \end{eqnarray*}$ .

also $\begin{eqnarray*} C=2 \end{eqnarray*}$ und $\begin{eqnarray*} n_0=4 \end{eqnarray*}$ .

26.01.2018, 18:49

blublablib

Auf diesen Beitrag antworten »

Vielen Dank ihr beiden! So kann ich zumindest den Teil der Aufgabe nachvollziehen Freude

Eine weitere Frage habe ich noch dazu: Wenn man nun
$\begin{eqnarray*} r_{kn}=\frac{n}{n-k}{{n-1}\choose{k}}\left(1-\frac{k-1}{n-1}\right)\left(1-\frac{k-1}{n-1}\right)\cdots \left(1-\frac{k-1}{n-k}\right) \end{eqnarray*}$
betrachtet. Dann kann ich den hinteren Teil abschätzen durch
$\begin{eqnarray*} 1\geq \left(1-\frac{k-1}{n-1}\right)\left(1-\frac{k-1}{n-1}\right)\cdots \left(1-\frac{k-1}{n-k}\right)>\left(1-\frac{k-1}{n-k}\right)^k=1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ .
Soweit so gut (Dank Eurer Hilfe eben Augenzwinkern

)

Aber dann geht's weiter mit einer Folgerung daraus, dass gilt
$\begin{eqnarray*} r_{kn}={{n-1}\choose {k}}\left( 1+\mathcal{O}\left(\frac{k^2}{n}\right)\right) \end{eqnarray*}$ .
Wieso gilt das? Was passiert mit dem Bruch vorne und wieso kann ich das $\begin{eqnarray*} > \end{eqnarray*}$ in der Abschätzung einfach übergehen?

Nochmal vielen Dank für Eure Hilfe!

29.01.2018, 08:49

HAL 9000

Auf diesen Beitrag antworten »

Wir reden hier von $\begin{eqnarray*} 1 \geq \ldots > 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ .

Die 1 links gehört trivialerweise natürlich auch zu $\begin{eqnarray*} 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ , so dass der mittlere Ausdruck $\begin{eqnarray*} \ldots \end{eqnarray*}$ durch diese Einschachtelung auch zu $\begin{eqnarray*} 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ gehört.

Und das $\begin{eqnarray*} \binom{n-1}{k} \end{eqnarray*}$ ist dann einfach nur ein Vorfaktor vor dem ganzen.

30.01.2018, 09:27

blublablib

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Wir reden hier von $\begin{eqnarray*} 1 \geq \ldots > 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ .

Die 1 links gehört trivialerweise natürlich auch zu $\begin{eqnarray*} 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ , so dass der mittlere Ausdruck $\begin{eqnarray*} \ldots \end{eqnarray*}$ durch diese Einschachtelung auch zu $\begin{eqnarray*} 1+\mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ gehört.

Das macht Sinn Augenzwinkern

Vielen Dank dafür!

Zitat:

Original von HAL 9000
Und das $\begin{eqnarray*} \binom{n-1}{k} \end{eqnarray*}$ ist dann einfach nur ein Vorfaktor vor dem ganzen.

Das mit dem Vorfaktor ist insofern einleuchtend, als dass ich den ja von der oberen Formel für $\begin{eqnarray*} r_{nk} \end{eqnarray*}$ übernehme. Aber wieso muss ich den Binomialkoeffizenten abschreiben und kann den Buch $\begin{eqnarray*} \frac{n}{n-k} \end{eqnarray*}$ weglassen? Wird der von dem Landau-Symbol "geschluckt"?
Meine Überlegung dazu ist die:
$\begin{eqnarray*} \frac{n}{n-k}=\frac{n-k+k}{n-k}=1+\frac{k}{n-k} \end{eqnarray*}$
und dann müsste ja der hintere Bruch auch in $\begin{eqnarray*} \mathcal{O}\left(\frac{k^2}{n}\right) \end{eqnarray*}$ sein. Ist das so?

30.01.2018, 09:55

HAL 9000

Auf diesen Beitrag antworten »

Ja, sogar nur $\begin{eqnarray*} \mathcal{O}\left(\frac{k}{n}\right) \end{eqnarray*}$ , wenn man das Landau-Symbol für diesen gemeinsamen Grenzübergang $\begin{eqnarray*} n,k \end{eqnarray*}$ so interpretiert, wie ich es oben getan habe (und wobei mir nach wie vor unwohl ist, weil von deiner Seite keinerlei wirkliche Rückkopplung zu dieser heiklen Frage gekommen ist).

30.01.2018, 11:45

blublablib

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
wenn man das Landau-Symbol für diesen gemeinsamen Grenzübergang $\begin{eqnarray*} n,k \end{eqnarray*}$ so interpretiert, wie ich es oben getan habe (und wobei mir nach wie vor unwohl ist, weil von deiner Seite keinerlei wirkliche Rückkopplung zu dieser heiklen Frage gekommen ist).

Ich denke schon, dass man das so annehmen kann, wie Du das gemacht hast. Denn das, was ich hier eingetragen habe, ist nur ein Auszug einer Aufgabe bzw. eines Papers (was wohl immer etwas problematisch ist, wenn man den Kontext nicht genau kennt... verwirrt

). Und Deine Interpretation fügt sich ganz gut in den Kontext ein.

Nochmals vielen Dank, Du hast mir sehr weitergeholfen!!

Neue Frage »

Antworten »

Rechnen mit Landau-Symbolen

Verwandte Themen