"zufallszahlen" rekursiv Def. < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:20 Mo 25.10.2010 | | Autor: | m0ppel |
| Aufgabe | 1. Wir untersuchen einen Erzeuger von Pseudozufallszahlen. Gegeben sind also [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] [mm]m[/mm]
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}[/mm] für alle [mm]k \ge k_{0}[/mm].
Finden Sie auch eine obere Schranke für [mm]l[/mm]. |
Ich weiß, dass die rekursiv definierte Folge beschränkt ist auf Grund der Eigenschaften von Modolus. Das heißt [mm] n_{k+1} [/mm] kann nicht größer werden als (m-1)
Ich habe gelesen, dass die Folge daher periodisch ist, aber wie kann ich das nachweisen?
Mein Ansatz wäre, zu zeigen, dass ein l [mm] \in \IN [/mm] existiert, welches folgende Eigenschaften hat:
[mm]n_{k}=n_{k+l} \gdw (n_{k-1}a_{0} + a_{1}) mod m = (n_{k+l}a_{0} + a_{1}) mod m[/mm]
aber wie kann ich hier weiter machen? Welche Rechenregeln muss man bei Modulo beachten?
Danke schon mal und Liebe Grüße!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:25 Mo 25.10.2010 | | Autor: | rainerS |
Hallo!
> 1. Wir untersuchen einen Erzeuger von Pseudozufallszahlen.
> Gegeben sind also [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] [mm]m[/mm]
> 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}[/mm] für
> alle [mm]k \ge k_{0}[/mm].
> Finden Sie auch eine obere Schranke für
> [mm]l[/mm].
> Ich weiß, dass die rekursiv definierte Folge beschränkt
> ist auf Grund der Eigenschaften von Modolus. Das heißt
> [mm]n_{k+1}[/mm] kann nicht größer werden als (m-1)
> Ich habe gelesen, dass die Folge daher periodisch ist,
> aber wie kann ich das nachweisen?
Tipp: Da alle Zufallszahlen kleiner als m sind, wie viele verschiedene Zufallszahlen kann es höchstens geben? Was passiert, wenn zum ersten Mal eine Zahl doppelt in der Folge auftaucht?
Viele Grüße
Rainer
|
|
|
|
