Wahrscheinlichkeit von ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:29 Do 19.04.2007 | | Autor: | wauwau |
| Aufgabe | Wie groß ist die Wahrscheinlichkeit, dass zwei beliebig gewählte natürliche Zahlen teilerfremd sind, d.h.
gesucht ist:
P(ggt(n,m)=1) |
wer weiß wie das geht?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:39 Do 19.04.2007 | | Autor: | felixf |
Hallo wauwau,
> Wie groß ist die Wahrscheinlichkeit, dass zwei beliebig
> gewählte natürliche Zahlen teilerfremd sind, d.h.
> gesucht ist:
>
> P(ggt(n,m)=1)
> wer weiß wie das geht?
muesstest du nicht erstmal sagen, welches Wahrscheinlichkeitsmass du auf [mm] $\IN \times \IN$ [/mm] verwendest? Andernfalls kann man das Mass von [mm] $\{ (x, y) \in \IN \times \IN \mid ggT(n, m) = 1 \}$ [/mm] nur schlecht bestimmen...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:01 Do 19.04.2007 | | Autor: | wauwau |
Ich nehme an,dass bei dieser Aufgabe der Grenzwert N-> [mm] \infty [/mm] des Produktes der endlichen eindimensionalen Wahrscheinlichkeitsmaße (Gleichverteilung in [1,2,...N]) der natürlichen Zahlen gemeint ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:02 Do 19.04.2007 | | Autor: | felixf |
> Ich nehme an,dass bei dieser Aufgabe der Grenzwert N->
> [mm]\infty[/mm] des Produktes der endlichen eindimensionalen
> Wahrscheinlichkeitsmaße (Gleichverteilung in [1,2,...N])
> der natürlichen Zahlen gemeint ist.
Also [mm] $\lim_{N\to\infty} \frac{|\{ (x, y) \mid 1 \le x, y \le N, ggT(x, y) = 1 \}|}{N^2}$? [/mm] Diese Frage gehoert zumindest eindeutig in die analytische Zahlentheorie...
Ein Ansatz ist vielleicht, dass man die Menge [mm] $\{ (x, y) \mid 1 \le x, y, \le N \}$ [/mm] in die Mengen [mm] $\{ (x, x) \mid 1 \le x \le N \}$, $\{ (x, y) \mid 1 \le x < y \le N \}$ [/mm] und [mm] $\{ (x, y) \mid 1 \le y < x \le N \}$ [/mm] unterteilt. Damit haette man [mm] $\lim_{N\to\infty} \frac{|\{ (x, y) \mid 1 \le x, y \le N, ggT(x, y) = 1 \}|}{N^2} [/mm] = [mm] \lim_{N\to\infty} \frac{1 + 2 |\{ (x, y) \mid 1 \le x < y \le N, ggT(x, y) = 1 \}|}{N^2} [/mm] = [mm] \lim_{N\to\infty} \frac{1 + 2 \sum_{y=2}^N \phi(y)}{N^2}$, [/mm] wobei [mm] $\phi$ [/mm] die Eulersche [mm] $\phi$-Funktion [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:27 Fr 20.04.2007 | | Autor: | wauwau |
und kennt man diesen Grenzwert oder die vorkommende summe (asymptotisch)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:59 Fr 20.04.2007 | | Autor: | Volker2 |
Hallo,
es gilt
[mm] \sum_{y\leq N}^N\phi(y)=\frac{3}{\pi^2}N^2+O(N\log [/mm] N), d.h.
$$
[mm] \lim_{N\to\infty} \frac{1 + 2 \sum_{y=2}^N \phi(y)}{N^2}= \frac{6}{\pi^2}=\frac{1}{\zeta(2)}
[/mm]
$$
Der Beweis der Asymptotik geht folgendermaßen:
[mm] \sum_{y\leq N}^N\phi(y)= \sum_{d\leq N,\ d|N}\mu(d)\sum_{m\leq \frac{N}{d}} [/mm] m
mit Möbiusinversion. Weiter mit bekannter arithmetischer Summenformel
[mm] =\sum_{d\leq N}\mu(d)\left( \frac{1}{2}\frac{N^2}{d^2}+O(\frac{N}{d})\right)
[/mm]
[mm] =\frac{N^2}{2} \sum_{d\leq N} \frac{\mu(d)}{d^2}+ O(N\log N)=\frac{N^2}{2}\frac{1}{\zeta(2)}+O(N\log [/mm] N)
nach nochmaliger Möbiusinversion zum den Kehrwert der Zetafunktion zu bestimmen.
Volker
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:43 So 22.04.2007 | | Autor: | wauwau |
Ich hab einen trivialeren Ansatz gefunden, den man glaube ich auch gelten lassen kann.
Sei p die gesuchte Wahrscheinlichkeit
Dann ist die Wahrschienlichkeit, dass ggt(a,b)=d
ja nichts anderes als die Wahrscheinlichkeit, dass (a teilbar durch d) und (b teilbar durch d) und [mm] (ggt(\bruch{a}{d},\bruch{b}{d}=1) [/mm]
dh:
P(ggt(a,b)=d)= [mm] \bruch{1}{d}*\bruch{1}{d}*p [/mm] = [mm] \bruch{p}{d^2}
[/mm]
Diese Wahrscheinlichkeiten aufsummiert über alle d muss natürlich 1 ergeben, also:
[mm] \summe_{d=1}^{\infty}\bruch{p}{d^2} [/mm] = 1
oder
[mm] p*\summe_{d=1}^{\infty}\bruch{1}{d^2} [/mm] = 1
und wie wir wissen ist die Summe genau [mm] \bruch{\pi^2}{6}
[/mm]
also die gewünschte Wahrscheinlichkeit
[mm] p=\bruch{6}{\pi^2}
[/mm]
Irgendwelche Fehler?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:27 So 22.04.2007 | | Autor: | Volker2 |
Hallo,
kannst Du mal den W-Raum [mm] \Omega [/mm] angeben, auf dem dein Wahrscheinlichkeitsmaß P definert sein soll? Ich weiß so aus dem Stehgreif nicht, wie der ausssieht.
Volker
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:51 So 22.04.2007 | | Autor: | wauwau |
Produkt der Wahrscheinlichkeitsräume, Gleichverteilung über den natürlichen Zahlen...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:17 So 22.04.2007 | | Autor: | felixf |
> Produkt der Wahrscheinlichkeitsräume, Gleichverteilung über
> den natürlichen Zahlen...
Wie sieht denn eine Gleichverteilung auf [mm] $\IN$ [/mm] aus?
Ich denke, wir haben hier [mm] $\Omega [/mm] = [mm] \IN \times \IN$ [/mm] und $P(A) = [mm] \lim_{n\to\infty} \frac{|A \cap \{ (x, y) \mid 1 \le x, y \le N \}|}{N^2}$. [/mm] Allerdings bin ich mir nicht sicher ob das wirklich ein Mass ist.
LG Felix
|
|
|
|
