Wie asymptotisch schlimm ist naives Mischen?

Es ist bekannt, dass dieser "naive" Algorithmus zum Mischen eines Arrays durch Tauschen jedes Elements mit einem zufällig ausgewählten nicht richtig funktioniert:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

Insbesondere gibt es, da bei jeder von Iterationen eine von Entscheidungen getroffen wird (mit einheitlicher Wahrscheinlichkeit), mögliche "Pfade" durch die Berechnung; weil die Anzahl der möglichen Permutationenteilt sich nicht gleichmäßig in die Anzahl der Pfade , es ist für diesen Algorithmus unmöglich, jedes der zu erzeugenPermutationen mit gleicher Wahrscheinlichkeit. (Stattdessen sollte man den sogenannten Fischer-Yates- Shuffle verwenden, der im Wesentlichen den Aufruf zur Auswahl einer Zufallszahl aus [0..n] und den Aufruf zur Auswahl einer Zufallszahl aus [i..n] ändert.) Das ist jedoch nicht meine Frage.) $n$ $n$ $n^n$ $n!$ $n^n$ $n!$

Was ich mich frage, ist, wie "schlecht" kann das naive Mischen sein? Insbesondere sei die Menge aller Permutationen und die Anzahl der Pfade durch den naiven Algorithmus, die die resultierende Permutation erzeugen , was ist das asymptotische Verhalten von funktionen $P(n)$ $C(\rho)$ $\rho\in P(n)$

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{\rho\in P(n)} C(\rho)$

und

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{\rho\in P(n)} C(\rho)$ ?

Der Hauptfaktor ist, diese Werte zu "normalisieren": Wenn das naive Mischen "asymptotisch gut" ist, dann

$\qquad \displaystyle \lim_{n\to\infty}M(n) = \lim_{n\to\infty}m(n) = 1$ .

Ich vermute (basierend auf einigen Computersimulationen, die ich gesehen habe), dass die tatsächlichen Werte von 1 abgegrenzt sind, aber ist es sogar bekannt, ob $\lim M(n)$ endlich ist oder ob $\lim m(n)$ abgegrenzt ist 0? Was ist über das Verhalten dieser Größen bekannt?

algorithms algorithm-analysis asymptotics probability-theory randomness Steven Stadnicki
quelle

Gute Frage. Ich weiß nicht, wo der beste Ort für diese Frage ist. Es sei denn, es ist klar, dass ein anderes Forum dafür besser ist. Ich denke, Sie sollten es eine Woche hier belassen. Wenn Sie keine zufriedenstellende Antwort erhalten, stellen Sie es in einem der anderen Foren (und setzen Sie Links in beide Fragen ).

Peter Shor

@vzn "Warum wird eine harte Analyse mit einem bekannten fehlerhaften Algorithmus durchgeführt?" Weil die Mathematik ist interessant, und man weiß nie, wo andere Anwendungen entstehen können - siehe Knuths Analyse von Bubble Sort, zum Beispiel. Atwoods Diagramme geben eine grobe qualitative Analyse der Inhomogenität, aber das ist weit entfernt von einer mathematisch quantitativen Analyse. (Und es gibt verschiedene äquivalente Formulierungen des Fischer-Yates-Shuffles - die erwähnte funktioniert einwandfrei.)

Steven Stadnicki

Für den Datensatz ist die OEIS-Sequenz A192053 maximal und listet keine geschlossene Form auf. Auch sind die Hinweise für diesen Eintrag legen nahe , dass min können sein , was bedeutet , dass .

C (ρ)

$C(\rho)$

C (ρ)

$C(\rho)$

2^{n - 1}

$2^{n-1}$

m (n) \to 0

$m(n) \rightarrow 0$

mhum

@vzn Was ist los mit offenen Fragen?

Yuval Filmus

@vzn Nicht einverstanden mit Ihrem letzten Satz, es gibt eine Menge Analysen von "unvollkommenen" Schlurfen. Wenn wir beispielsweise zufällige Transpositionen vornehmen, ist bekannt, dass der Schwellenwert für die Zufälligkeit ungefähr . Die vorliegende Frage mag schwierig sein, aber a priori ist es schwierig zu sagen, ob es "sehr schwer" ist. Eine Antwort wie die von mhum ist bereits sehr befriedigend und zeigt, dass die Frage für das Forum angemessen war und keine unüberwindliche Barriere darstellte (formelle Beweise wurden beiseite gelegt).

(1 / 2) n \log n

$(1/2) n\log n$

Yuval Filmus

Antworten:

Wir werden durch Induktion zeigen, dass die Permutation ein Beispiel mit . Wenn dies der schlimmste Fall ist, wie es bei den ersten der Fall ist (siehe die Hinweise zur OEIS-Sequenz A192053 ), dann ist . Das normalisierte Minimum ist also wie das normalisierte Maximum "exponentiell schlecht". $\rho_n = (2,3,4,\ldots, n,1)$ $C(\rho_n) = 2^{n-1}$ $n$ $m(n) \approx (2/e)^{n}$

Der Grundfall ist einfach. Für den Induktionsschritt brauchen wir ein Lemma:

Lemma: In jedem Pfad von zu werden die Positionen und des ersten Zuges oder des letzten Zuges getauscht und . $(2,3,4, \ldots, n, 1)$ $(1,2,3, \ldots, n)$ $1$ $n$ $1$ $n$

Beweisskizze: Angenommen, nicht. Betrachten Sie den ersten Zug, bei dem es um die -te Position geht. Angenommen, es ist der -te Zug, und . Dieser Zug muss den Gegenstand an die -te Stelle setzen. Betrachten Sie nun den nächsten Zug, der den Gegenstand berührt . Angenommen, dieser Zug ist der -te Zug. Dieser Zug muss und tauschen und den Gegenstand an die -te Stelle verschieben, mit . Ein ähnliches Argument besagt, dass der Punkt erst nachträglich nach rechts verschoben werden kann. Aber der Punkt $n$ $i$ $i\neq 1$ $i \neq n$ $1$ $i$ $1$ $j$ $i$ $j$ $1$ $j$ $i < j$ $1$ $1$ Muss in erster Linie ein Widerspruch enden. $\square$

Wenn der erste Zug die Positionen und vertauscht, müssen die verbleibenden Züge die Permutation bis annehmen . Wenn die verbleibenden Züge die erste Position nicht berühren, ist dies die Permutation in Position , und wir wissen durch Induktion, dass es Pfade, die dies tun. Ein Argument, das dem Beweis des Lemma ähnlich ist, besagt, dass es keinen Pfad gibt, der die erste Position berührt, da der Punkt dann in der falschen Position enden muss. $1$ $n$ $(1, 3,4,5, \ldots, n,2)$ $(1,2,3,4, \ldots, n)$ $\rho_{n-1}$ $2 \ldots n$ $C(\rho_{n-1})=2^{n-2}$ $1$

Wenn der letzte Zug die Positionen und vertauscht , müssen die ersten Züge die Permutation zur Permutation . Wiederum, wenn diese Bewegungen die letzte Position nicht berühren, dann ist dies die Permutation , und durch Induktion gibt es Pfade das macht es. Und wieder, wenn einer der ersten Züge hier die letzte Position berührt, kann der Gegenstand niemals an der richtigen Stelle landen. $1$ $n$ $n-1$ $(2,3,4,\ldots, n,1)$ $(n,2, 3,4, \ldots, n-1, 1)$ $\rho_{n-1}$ $C(\rho_{n-1})=2^{n-2}$ $n-1$ $1$

Somit ist . $C(\rho_n) = 2C(\rho_{n-1}) = 2^{n-1}$

Peter Shor
quelle

Perfekt - das Argument hinter dem Lemma ähnelt dem, das ich für die Involvierung als einzige Möglichkeit hatte, die Identitätspermutation zu erhalten, aber ich hatte die rekursive Struktur beim expliziten Tausch verpasst. Vielen Dank!

Steven Stadnicki

Nach einigem Stöbern dank Mhums Zeiger auf OEIS habe ich endlich eine exzellente Analyse und ein nettes (relativ) elementares Argument gefunden (soweit ich das beurteilen kann, an Goldstein und Moews [1]), dass wächst superexponentiell schnell in : $M(n)$ $n$

Jede Involution von entspricht einem Durchlauf des 'naiven' Mischalgorithmus, der die Identitätspermutation als Ergebnis erzeugt, da der Algorithmus mit und anschließend mit , beide unverändert bleibt. Dies bedeutet, dass die Anzahl der Läufe des Algorithmus, die die Identitätspermutation ergeben, mindestens die Anzahl der Involutionen (in der Tat zeigt eine kleine Überlegung, dass die Entsprechung 1-1 ist und es genau ). und so wird das Maximum in von unten durch . $\iota$ $\{1\ldots n\}$ $k$ $\iota(k)$ $\iota(k)$ $k$ $Q(n)$ $Q(n)$ $M(n)$ $Q(n)$

$Q(n)$ anscheinend eine Reihe von Namen, einschließlich der Telefonnummern : siehe http://oeis.org/A000085 und http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29 . Die Asymptoten sind wohlbekannt, und es stellt sich heraus, dass ; Aus der Wiederholungsrelation kann induktiv gezeigt werden, dass das Verhältnis erfüllt und von dort erhält die Basisanalyse den führenden Term in der Asymptotik, obwohl der andere Begriffe erfordern eine vorsichtigere Anstrengung. Da der "Skalierungsfaktor" $Q(n) \approx C\left(\frac{n}{e}\right)^{n/2}e^\sqrt{n}$ $Q(n) = Q(n-1)+(n-1)Q(n-2)$ $R(n) = \frac{Q(n)}{Q(n-1)}$ $\sqrt{n}\lt R(n)\lt\sqrt{n+1}$ $n^{n/2}$ $\frac{n!}{n^n}$ in der Definition von handelt es sich nur um , der führende Term von dominiert und ergibt (asymptotisch) . $M(n)$ $C\sqrt{n}e^{-n}$ $Q(n)$ $M(n)\geq Cn^{(n+1)/2}e^{-3n/2+\sqrt{n}}$

Tatsächlich zeigen Goldstein und Moews in [1], dass die Identitätspermutation für große am wahrscheinlichsten ist , daher ist in der Tat a und das Verhalten von ist vollständig festgelegt. Damit bleibt die Frage nach dem Verhalten von offen; Es würde mich nicht überraschen, wenn dies auch der Analyse in ihrem Artikel entspräche, aber ich hatte noch keine Gelegenheit, sie genau genug zu lesen, um ihre Methoden wirklich in den Griff zu bekommen, nur genug, um das grundlegende Ergebnis herauszufinden. $n$ $\geq$ $\approx$ $M(n)$ $m(n)$

[1] Goldstein, D. und Moews, D .: "Die Identität ist die wahrscheinlichste Austauschmischung für großes n", http://arxiv.org/abs/math/0010066

Steven Stadnicki
quelle

Es ist nicht schwer zu zeigen, dass die Permutation ein Beispiel mit . Wenn dies der schlechteste Fall ist, wie es für die ersten paar der Fall ist , dann ist .

(2, 3, 4, \dots, n, 1)

$(2,3,4,\ldots,n,1)$

C (ρ) = 2^{n - 1}

$C(\rho) = 2^{n-1}$

n

$n$

m (n) \approx (2 / e)^{n}

$m(n) \approx (2/e)^n$

Peter Shor

@PeterShor Kannst du das grundlegende Argument geben? Ich habe das Gefühl, ich vermisse eine einfache Version des Involvutions-Arguments, die funktionieren würde, aber ich verstehe es nicht ganz. Ich denke, auch wenn das nicht ganz minimal ist, wäre das gut genug. Es ist unwahrscheinlich, dass die minimale Anzahl in

subexponentiell ist, und nur zu wissen, dass sowohl das normalisierte Maximum als auch das minimale "exponentiell schlecht" sind, ist eine ziemlich zufriedenstellende Antwort.

n

$n$

Steven Stadnicki

Ich habe eine Antwort mit dem Argument hinzugefügt ... es ist zu lang für einen Kommentar.

Peter Shor