Lineare Kongruenzmethode < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wir untersuchen einen Erzeuger von Pseudozufallszahlen. Gegeben sind [mm] a_{0}, a_{1} [/mm] und [mm] m,n_{0} [/mm] und für [mm] k\in \IN_{0} [/mm] wird [mm] n_{k+1} [/mm] rekursiv durch
[mm] n_{k+1}=(n_{k}*a_{0}+a_{1})mod [/mm] m
definiert. Man beweise, dass die Folge [mm] n_{k} [/mm] schließlich periodisch wird. Es gibt [mm] k_{0},l \in \IN, [/mm] so dass
[mm] n_{k+l}=n_{k} \forall k\ge k_{0}.
[/mm]
Finden Sie auch eine obere Schranke für l. |
Durch probieren weiß ich bereits, dass die Aussage stimmen muss und die Schranke der Folge m ist und für l somit gilt l [mm] \le [/mm] m-k.
Aber ich das beides jetzt beweisen soll, dass seh ich grade überhaupt nicht.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:39 Mo 19.10.2009 | | Autor: | felixf |
Hallo!
> Wir untersuchen einen Erzeuger von Pseudozufallszahlen.
> Gegeben sind [mm]a_{0}, a_{1}[/mm] und [mm]m,n_{0}[/mm] und für [mm]k\in \IN_{0}[/mm]
> wird [mm]n_{k+1}[/mm] rekursiv durch
> [mm]n_{k+1}=(n_{k}*a_{0}+a_{1})mod[/mm] m
> definiert. Man beweise, dass die Folge [mm]n_{k}[/mm] schließlich
> periodisch wird. Es gibt [mm]k_{0},l \in \IN,[/mm] so dass
> [mm]n_{k+l}=n_{k} \forall k\ge k_{0}.[/mm]
> Finden Sie auch eine
> obere Schranke für l.
> Durch probieren weiß ich bereits, dass die Aussage
> stimmen muss und die Schranke der Folge m ist und für l
> somit gilt l [mm]\le[/mm] m-k.
> Aber ich das beides jetzt beweisen soll, dass seh ich
> grade überhaupt nicht.
Machen wir das mal etwas abstrakter. Du hast eine endliche Menge $M$ mit $m$ Elementen (naemlich $0, [mm] \dots, [/mm] m - 1$), und du hast eine Funktion $f : M [mm] \to [/mm] M$ (naemlich $x [mm] \mapsto [/mm] (x [mm] \cdot a_0 [/mm] + [mm] a_1) \mod [/mm] m$).
Jetzt definierst du damit eine Folge [mm] $a_{k+1} [/mm] := [mm] f(a_k)$ [/mm] fuer $k [mm] \in \IN_{>0}$ [/mm] in $M$, naemlich [mm] $(a_k)_{k\in\IN}$.
[/mm]
Wieso wird die Folge schliesslich periodisch, und was ist eine obere Schranke fuer die Periodenlaenge?
Du musst zeigen, dass es $i < j$ gibt mit [mm] $a_i [/mm] = [mm] a_j$: [/mm] dann folgt, dass die Folge periodisch ist (wobei die minimale Periodenlaenge $j - i$ teilt). Dazu: was folgt fuer $M$ (bzw. $|M|$), wenn es keine solche $i$ und $j$ gibt?
Wenn du das herausgefunden hast, sollte die obere Schranke fuer die Periodenlaenge auch kein Problem mehr sein.
LG Felix
|
|
|
| |
|
Ich verstehe schon, dass bei einer endlichen Menge von Zahlen sich irgendwann etwas wiederholen muss, aber wieso muss das periodisch passieren? Wobei man bei der Modulorechnung natürlich annehmen kann, dass wenn sich wirklich zuerst das erste Element wiederholt, dann folgt die Periodizität automatisch. Aber was ist, wenn es nicht das erste Element ist? Wenn sich nach dem Element [mm] a_{j} [/mm] das Element [mm] a_{i} [/mm] wiederholt und nicht [mm] a_{1}? [/mm] Muss ich den Fall ausschließen? Oder reicht es, dass die Folge periodisch wird, egal mit welchem Anfangsglied? Dann wäre es klar. Denn irgendwann muss sich bei einer endlichen Ergebnissmenge ein Element wiederholen und da Modulorechnung mit der Teilbarkeit zusammenhängt, muss es ab dem wiederholten Element periodisch werden. Und dies muss spätestens nach m Schritten geschehen, da man nur m Elemente zur Auswahl hat. Oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:12 Mo 19.10.2009 | | Autor: | felixf |
Hallo!
> Ich verstehe schon, dass bei einer endlichen Menge von
> Zahlen sich irgendwann etwas wiederholen muss, aber wieso
> muss das periodisch passieren?
Weil der neue Status der Funktionswert des alten Status ist, wobei die Funktion (hier: $f$) nicht von der Schrittanzahl oder so etwas abhaengt. Wenn also die Folge das zweite Mal das Element $x$ annimmt, ist das naechste Element (wie beim ersten Mal) $f(x)$, das Element danach wieder $f(f(x))$, etc.
Es passiert also ab beiden Punkten genau das gleiche.
> Wobei man bei der
> Modulorechnung natürlich annehmen kann, dass wenn sich
> wirklich zuerst das erste Element wiederholt, dann folgt
> die Periodizität automatisch. Aber was ist, wenn es nicht
> das erste Element ist? Wenn sich nach dem Element [mm]a_{j}[/mm] das
> Element [mm]a_{i}[/mm] wiederholt und nicht [mm]a_{1}?[/mm]
Siehe oben: das kann sehr wohl vorkommen und ist voellig normal.
> Denn irgendwann muss sich bei einer endlichen
> Ergebnissmenge ein Element wiederholen und da
> Modulorechnung mit der Teilbarkeit zusammenhängt, muss es
> ab dem wiederholten Element periodisch werden.
Das hat mit der Modulorechnung und Teilbarkeit wirklich nichts zu tun.
> Und dies muss spätestens nach m Schritten geschehen, da man nur m
> Elemente zur Auswahl hat. Oder?
Ja.
LG Felix
|
|
|
| |
|
> Ich verstehe schon, dass bei einer endlichen Menge von
> Zahlen sich irgendwann etwas wiederholen muss, aber wieso
> muss das periodisch passieren? Wobei man bei der
> Modulorechnung natürlich annehmen kann, dass wenn sich
> wirklich zuerst das erste Element wiederholt, dann folgt
> die Periodizität automatisch. Aber was ist, wenn es nicht
> das erste Element ist? Wenn sich nach dem Element [mm]a_{j}[/mm] das
> Element [mm]a_{i}[/mm] wiederholt und nicht [mm]a_{1}?[/mm]
Weshalb die [mm] a_i [/mm] etc ?
[mm] a_0 [/mm] und [mm] a_1 [/mm] sind vorgegebene Faktoren, welche nicht
den Anfang einer Zahlenfolge [mm] a_0,a_1,a_2,.... [/mm] bilden !
Die erzeugte "Zufallszahlenfolge" ist die der [mm] n_k (n\in\IN) [/mm] .
> Muss ich den Fall
> ausschließen? Oder reicht es, dass die Folge periodisch
> wird, egal mit welchem Anfangsglied?
Es geht nur um Periodizität ab einer bestimmten
Stelle der Folge. Es könnte ja allenfalls sein, dass
einige Elemente, welche vor der periodischen
Entwicklung vorkommen, später nicht mehr auf-
treten.
> Dann wäre es klar.
> Denn irgendwann muss sich bei einer endlichen
> Ergebnismenge ein Element wiederholen und da
> Modulorechnung mit der Teilbarkeit zusammenhängt, muss es
> ab dem wiederholten Element periodisch werden. Und dies
> muss spätestens nach m Schritten geschehen, da man nur m
> Elemente zur Auswahl hat. ![[ok]](/images/smileys/ok.gif "[ok]")
LG
|
|
|
|
