Integral ist approximativ log < Integration < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:46 Do 13.06.2019 | | Autor: | Septime |
| Aufgabe | | Sei [mm] \(0\le K_N [/mm] < [mm] N_{\gamma}\)\sim\(N\) [/mm] und [mm] \(0
[mm] \[ \int_{0}^{N_{\gamma}} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy \sim log(N_\gamma)\] [/mm] für [mm] $N\to \infty [/mm] |
Mir wurde der Beweis schon erklärt, aber ich verstehe es noch nicht ganz. Man lässt [mm] \(K_n \to \infty\) [/mm] langsam. Dann unterteilen wir es in 3 Intervalle [mm] \([0,K_N],[K_N,N_{\gamma}/logN] [/mm] und [mm] [N\gamma/logN,N\gamma]\). [/mm] Mit [mm] \((1-(1-y/N_{\gamma})^{N_{\gamma}}) \to 1\) [/mm] außerhalb des ersten Intervalls und [mm] \((1-y/N_{\gamma})^{n-1} \to 1\) [/mm] außerhalb des 3ten Intervalls erhalten wir
[mm] $\int_{0}^{N_{\gamma}} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy= O(K_N) [/mm] + [mm] \int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy [/mm] + O(loglogN)$
Das die rechte Seite ungefähr log(N) ist sehe ich.
Ich sehe zum Beispiel auch , dass
[mm] $$\int_{K_N}^{N_\gamma/logN} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy \le \int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy$$
[/mm]
ist, weil die beiden Terme nach oben durch 1 abgeschätzt werden können, aber ich verstehe nicht, warum die beiden Integrale das gleiche sein sollen bzw. warum die beiden Terme ignoriert werden können und wir [mm] $$\int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy$$ [/mm] schreiben können ohne die Grenzen zu unendlich zu ändern.
|
|
| |
|
Hiho,
na dann wollen wir mal…
> Mir wurde der Beweis schon erklärt, aber ich verstehe es
> noch nicht ganz. Man lässt [mm]\(K_n \to \infty\)[/mm] langsam.
Ich vermute du meinst [mm] $K_N \to \infty$ [/mm] und $0 < n < [mm] N_\gamma$ [/mm] ist fix, oder?
> Dann unterteilen wir es in 3 Intervalle [mm]\([0,K_N],[K_N,N_{\gamma}/logN][/mm] und [mm][N\gamma/logN,N\gamma]\)[/mm]
Ok
> Mit [mm]\((1-(1-y/N_{\gamma})^{N_{\gamma}}) \to 1\)[/mm] außerhalb des ersten Intervalls
Das sehe ich noch nicht.
Ich komme drauf, dass man zeigen müsste [mm] $\left(1 - \frac{K_N}{N_\gamma}\right)^{N_\gamma} \to [/mm] 1$ und ich sehe bisher noch nicht, wieso das gelten sollte…
Vllt. hast du ja einen anderen Ansatz.
> und [mm]\((1-y/N_{\gamma})^{n-1} \to 1\)[/mm] außerhalb des 3ten Intervalls
Das krieg ich auch, allerdings nur unter der obigen Annahme, dass du [mm] $K_N \to \infty$ [/mm] meintest und $n$ beliebig, aber fix ist.
> erhalten wir [mm]\int_{0}^{N_{\gamma}} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy= O(K_N) + \int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy + O(loglogN)[/mm]
Das sehen wir nach den beantworteten Fragen 
> Das die rechte Seite ungefähr log(N) ist sehe ich.
Echt? Also dass [mm] $O(\log\log [/mm] N) [mm] \subset O(\log [/mm] N)$ gilt, ist klar.
Aber wieso sollte [mm] K_N [/mm] nicht schneller wachsen als [mm] $\log [/mm] N$?
> Ich sehe zum Beispiel auch , dass
> [mm]\int_{K_N}^{N_\gamma/logN} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy \le \int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy[/mm]
>
> ist, weil die beiden Terme nach oben durch 1 abgeschätzt werden können
Ja, das ist trivial.
> aber ich verstehe nicht, warum die beiden Integrale das gleiche sein sollen
Das sollen sie ja gar nicht, sie sollen nur asymptotisch gleich schnell wachsen
> bzw. warum die beiden Terme ignoriert werden können und wir
> [mm]\int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy[/mm] schreiben
> können ohne die Grenzen zu unendlich zu ändern.
Also nehmen wir mal an, es sei [mm] $O(K_N) \subset O(\log [/mm] N)$ (siehe meine Frage oben), dann gilt schlichtweg:
[mm]O\left(\int_{0}^{N_{\gamma}} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy\right) = O\left(O(K_N) + \int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy + O(loglogN)\right) = O\left( \int_{K_N}^{N_{\gamma}/log N} \frac{1}{y}dy\right)[/mm]
Oder mal einfacher mit Funktionen ausgedrückt: Gilt $f [mm] \in [/mm] O(g)$ so ist [mm] $O(f\,+\,g) [/mm] = O(g)$
edit: Vielleicht fällt es ja auch leichter mit der Methode das substituierte Integral aus meiner zweiten Antwort zu betrachten:
$ [mm] \int_{0}^{1} \frac{1}{1-z}(1-z^{N_{\gamma}})z^{n-1}dy$ [/mm]
Gruß,
Gono
|
|
|
| |
|
Hiho,
mal ein einfacherer und elementarer Ansatz, der (erstmal) voraussetzt [mm] $N_\gamma \in \IN$, [/mm] aber das ist nicht wirklich eine Einschränkung:
Wir haben:
[mm] $\color{blue}{\int_{0}^{N_{\gamma}} \frac{1}{y}(1-(1-y/N_{\gamma})^{N_{\gamma}})(1-y/N_{\gamma})^{n-1}dy} [/mm] $
Nun substituieren wir [mm] $z=1-\frac{y}{N_{\gamma}}$ [/mm] und erhalten:
[mm] $\color{blue}{ \int_{0}^{1} \frac{1}{1-z}(1-z^{N_{\gamma}})z^{n-1}dy} [/mm] $
Für [mm] $N_\gamma \in \IN$ [/mm] gilt: [mm] $\frac{1-z^{N_{\gamma}}}{1-z} [/mm] = 1 + z + [mm] \ldots [/mm] + [mm] z^{N_{\gamma} - 1} [/mm] = [mm] \sum_{k=0}^{N_{\gamma} - 1} z^k$
[/mm]
Und damit erhalten wir für das Integral:
[mm] $\color{blue}{\sum_{k=0}^{N_{\gamma} - 1} \int_0^1 z^{n+k-1} dz}$
[/mm]
$= [mm] \color{blue}{\sum_{k=0}^{N_{\gamma} - 1} \frac{1}{n+k}}$
[/mm]
$= [mm] \color{blue}{H(N_\gamma + n - 1) - H(n)}$
[/mm]
wobei H(n) die n-te Partialsumme der ![[]](/images/popup.gif) harmonischen Reihe bezeichnet.
Und für die gilt bekanntlich: $H(n) [mm] \sim \log [/mm] n$
Na den Rest schaffst du jetzt hoffentlich alleine...
Gruß,
Gono
|
|
|
|
