Zahlen tauschen

17.08.2017, 09:47

hibu

Zahlen tauschen

Meine Frage:
Hallo zusammen

Ich habe die Buchstaben A,B,C,D,E und soll die zufällig anordnen,
so dass jeder Buchstabe mit möglichst gleicher Wahrscheinlichkeit (20%) an jeder Stelle stehen kann

Dazu fange ich mit A,B,C,D,E an und vertausche mit p=0.5 zwei Buchstaben
zB die ersten zwei
Nach einem Durchgang könnte das dann so aussehen B,A,C,D,E

Ich kann zwei beliebige Positionen nehmen und die Buchstaben dort mit p=0.5 tauschen und das beliebig oft wiederholen

Meine Frage ist jetzt wie und wie oft ich tauschen muss,dass die Anordnung der Zahlen zufällig ist

Vielen Dank für Hinweise

Meine Ideen:
Ich habe 5 Tauschvorgänge an folgenden Positionen
1 und 5
3 und 4
2 und 3
1 und 4
2 und 5

So habe ich jede Stelle zweimal

und das dann 10000 mal wiederholt.Dann kommt auch die Wahrscheinlichkeit von 20% ganz gut hin

Mich würde interessieren ob man das optimieren kann

17.08.2017, 10:11

HAL 9000

Auf diesen Beitrag antworten »

Bei insgesamt $\begin{align*} n \end{align*}$ Buchstaben (bei dir n=5) kommt man mit maximal $\begin{align*} n-1 \end{align*}$ Vertauschungen aus, wenn man sie so organisiert:

Für $\begin{align*} k=n,n-1,\ldots,2 \end{align*}$ wählt man jeweils eine Position $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,\ldots,k\} \end{align*}$ und tauscht dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} k \end{align*}$ (im Fall j=k ist da natürlich nichts zu tun).

Mit diesem Simulationsverfahren erreicht man eine Gleichverteilung auf der Menge der $\begin{align*} n! \end{align*}$ Permutationen.

Bei deinem Verfahren verbunden mit einer festen (deterministischen) Wahl der Tauschpositionen und jeweils Wahrscheinlichkeit p=0.5 des Tausches erreicht man nie Gleichverteilung, zumindest nicht im Fall $\begin{align*} n\geq 3 \end{align*}$ . Die Begründung ist ganz einfach die: Bei insgesamt $\begin{align*} m \end{align*}$ Tauschversuchen kann man das ganze mit einem Laplaceschen W-Raum der Dimension $\begin{align*} 2^m \end{align*}$ modellieren, wo sämtliche Ereignisse eine Wahrscheinlichkeit besitzen, die ein Vielfaches von $\begin{align*} \frac{1}{2^m} \end{align*}$ sind. Nun ist aber das angestrebte $\begin{align*} \frac{1}{n!} \end{align*}$ im Fall $\begin{align*} n\geq 3 \end{align*}$ nie ein ganzzahliges Vielfaches eines Wertes $\begin{align*} \frac{1}{2^m} \end{align*}$ , für kein $\begin{align*} m \end{align*}$ . Man kann mit großen $\begin{align*} m \end{align*}$ beliebig nahe kommen, erreicht es aber nicht.

17.08.2017, 13:00

hibu

Auf diesen Beitrag antworten »

Danke schonmal
Das habe ich aber noch nicht ganz verstanden.Ist nur Schulmathematik

Ich wähle eine Position zufällig aus und tausche die dann mit dem Buchstaben an der Stelle 5
und das mache ich n-1 also 4mal?

17.08.2017, 13:18

HAL 9000

Auf diesen Beitrag antworten »

Lies bitte genau durch:

Zitat:

Original von HAL 9000
Für $\begin{align*} k=n,n-1,\ldots,2 \end{align*}$ wählt man jeweils eine Position $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,\ldots,k\} \end{align*}$ und tauscht dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} k \end{align*}$ (im Fall j=k ist da natürlich nichts zu tun).

In deinem Fall n=5 bedeutet das nacheinander in genau der Reihenfolge:

k=5: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,3,4,5\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 5 \end{align*}$ .
k=4: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,3,4\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 4 \end{align*}$ .
k=3: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,3\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 3 \end{align*}$ .
k=2: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 2 \end{align*}$ .

---------------------------------------------------------------------------------

Was dein ursprüngliches Verfahren betrifft:

Zitat:

Original von hibu
Ich habe 5 Tauschvorgänge an folgenden Positionen
1 und 5
3 und 4
2 und 3
1 und 4
2 und 5

So habe ich jede Stelle zweimal

und das dann 10000 mal wiederholt.

da kannst du getrost 10000 durch 25 ersetzen, dann ist die Genauigkeit der simulierten Verteilung bereits in der Größenordnung der üblichen Floatingpoint-Zahlen (d.h. ungefähr $\begin{align*} 10^{-16} \end{align*}$ ). Ist mit 5*25=125 "Münzwürfen" zwar immer noch ineffizienter als das obige direkte Verfahren, aber schon deutlich zügiger als mit 10000 Runden. Augenzwinkern

17.08.2017, 16:47

hibu

Auf diesen Beitrag antworten »

Danke
Jetzt ist es klar geworden
Das Problem ist nur,dass das ein ganz anderes Programm ist
Da muss man völlig neu programmieren

17.08.2017, 16:54

HAL 9000

Auf diesen Beitrag antworten »

Die Anmerkung zur Beschleunigung deiner Methode hast du wohl nicht gelesen? Aus 10000 dann 25 zu machen, kann doch nicht so schwer sein. Augenzwinkern

17.08.2017, 17:18

hibu

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Die Anmerkung zur Beschleunigung deiner Methode hast du wohl nicht gelesen? Aus 10000 dann 25 zu machen, kann doch nicht so schwer sein. Augenzwinkern

Das ist nicht so schwer Augenzwinkern

Ich meinte dein Tauschverfahren das ist ein ganz anderes Programm

Zitat:

Original von HAL 9000
In deinem Fall n=5 bedeutet das nacheinander in genau der Reihenfolge:

k=5: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,3,4,5\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 5 \end{align*}$ .
k=4: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,3,4\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 4 \end{align*}$ .
k=3: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2,3\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 3 \end{align*}$ .
k=2: Wähle $\begin{align*} j \end{align*}$ gleichverteilt aus $\begin{align*} \{1,2\} \end{align*}$ und tausche dann die Werte an den Positionen $\begin{align*} j \end{align*}$ und $\begin{align*} 2 \end{align*}$ .

Hier habe ich noch eine Frage
Läuft das nur einmal durch? 4 Schritte und fertig?

17.08.2017, 17:19

HAL 9000

Auf diesen Beitrag antworten »

Für eine zu simulierende Permutation: Ja.

17.08.2017, 17:22

hibu

Auf diesen Beitrag antworten »

Vielen Dank smile

Neue Frage »

Antworten »

Zahlen tauschen

Verwandte Themen