Pseudozufallszahlen/periodisch

16.10.2009, 14:32

Streifchen

Pseudozufallszahlen/periodisch

Hallo ihr,
ich soll beweisen, dass die Folge zum Erzeugen von Peseudozufallszahlen periodisch wird. dass das so ist, ist mir klar. Ich hab gedacht, man könne da mit vollständiger Induktion rangehen, aber ich komme nicht weit.

Hier nochmal die Aufgabe,

gegeben sind $\begin{eqnarray*} a_0,a_1,m,n,k \in \mathbb N \end{eqnarray*}$ und die Folge
$\begin{eqnarray*} n_{k+1} = (n_k a_0 + a_1) mod \;m \end{eqnarray*}$

zu zeigen ist, dass sie periodisch wird also
$\begin{eqnarray*} \exists k_0, l \in \mathbb N \end{eqnarray*}$ , sodass $\begin{eqnarray*} n_{k+l}=n_k\quad; \forall k\geq k_0 \end{eqnarray*}$

vielleicht kann mir ja jemand helfen

lg Streifchen

16.10.2009, 14:45

Auf diesen Beitrag antworten »

Aufgrund der Rekursion genügt es zu zeigen, dass es überhaupt zwei Indizes $\begin{eqnarray*} r<s \end{eqnarray*}$ mit $\begin{eqnarray*} n_r = n_s \end{eqnarray*}$ gibt. (*)

Denn aufgrund der Rekursion folgt dann auch $\begin{eqnarray*} n_{r+1} = n_{s+1}, n_{r+2} = n_{s+2}, \ldots \end{eqnarray*}$ usw., also $\begin{eqnarray*} n_{k+l}=n_k \end{eqnarray*}$ für alle $\begin{eqnarray*} k\geq r \end{eqnarray*}$ mit $\begin{eqnarray*} l:=s-r \end{eqnarray*}$ .

Und (*) folgt unmittelbar aus dem Schubfachprinzip, angewandt auf $\begin{eqnarray*} n_0,n_1,\ldots,n_m \end{eqnarray*}$ .

16.10.2009, 14:53

Streifchen

Auf diesen Beitrag antworten »

hallo,

was ist das schubfachprinzip?

16.10.2009, 15:00

Auf diesen Beitrag antworten »

Solltest du eigentlich kennen, ansonsten frag mal Freund Google oder Wiki.

16.10.2009, 15:07

Streifchen

Auf diesen Beitrag antworten »

ah ok,

also weil ich mehr zahlen erzeugen will als ich mod (dafür hab ich ja nur die zahlen 1-9 zur verfügung) rechnen kann muss ich zwangsläufig wieder vorne anfangen????

16.10.2009, 15:10

Auf diesen Beitrag antworten »

Zitat:

Original von Streifchen
(dafür hab ich ja nur die zahlen 1-9 zur verfügung)

Ich sehe da zunächst nur ein $\begin{eqnarray*} \bmod m \end{eqnarray*}$ , also mit den $\begin{eqnarray*} m \end{eqnarray*}$ Resten $\begin{eqnarray*} 0,1,\ldots,m-1 \end{eqnarray*}$ .

Zitat:

Original von Streifchen
rechnen kann muss ich zwangsläufig wieder vorne anfangen????

Nicht notwendig "von vorn", das sagt das Schubfachprinzip nicht - und ist ja hier auch gar nicht nötig.

16.10.2009, 15:17

Streifchen

Auf diesen Beitrag antworten »

ok,

das heißt, dass aber m fest ist. und irgendwann werde ich doch mehr zahlen erzeugen als m groß ist, oder?? und dann setzt das schubfachprinzip ein?!?!?

16.10.2009, 15:22

Auf diesen Beitrag antworten »

Muss ich dir denn jeden kleinen Gedanken abnehmen?

Zitat:

Original von Arthur Dent
Schubfachprinzip, angewandt auf $\begin{eqnarray*} n_0,n_1,\ldots,n_m \end{eqnarray*}$ .

Das sind bereits $\begin{eqnarray*} m+1 \end{eqnarray*}$ Reste aus dem Bereich $\begin{eqnarray*} 0,1,\ldots,m-1 \end{eqnarray*}$ , also sind nach Schubfachprinzip bereits zwei dieser Werte gleich. Hier schon, nicht "irgendwann"!

16.10.2009, 15:28

Streifchen

Auf diesen Beitrag antworten »

naja etwas dümmlich ausgedrückt, meinte ich das.
Entschuldige bitte, wenn ich dich nerve.

ich hab das glaube ich verstanden.

lg Streifchen

16.10.2009, 16:11

Auf diesen Beitrag antworten »

Ja, das ist wahrscheinlich eine Mentalitätsfrage: Ich denke immer gern etwas länger nach, bevor ich nachfrage oder antworte - hat mir früher in meiner Schulzeit öfter den Vorwurf "schlechter Mitarbeit" gebracht - und wahrscheinlich erwarte ich das unbewusst auch von anderen. Augenzwinkern

Neue Frage »

Antworten »

Pseudozufallszahlen/periodisch

Verwandte Themen