scientific article; zbMATH DE number 1052336
Central limit and other weak theorems (60F05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Renewal theory (60K05) Applications of renewal theory (reliability, demand theory, etc.) (60K10)
Ausgehend von der Analyse der Anzahl der Vergleiche \(X_n\), die Varianten des bekannten Sortieralgorithmus Quicksort zum Sortieren einer Liste der Länge \(n\) benötigen, erhalten wir folgendes allgemeine Resultat: Betrachte Folgen von Zufallsvariablen \((X_n)_{n\in\mathbb{Z}^+}\) und \((\overline X_n)_{n\in\mathbb{Z}^+}\) mit Werten in \(\mathbb{Z}^+\), und \((Z_n)_{n\geq n_0}\) mit Werten jeweils in \(\{1,\dots,n\}\). Die \(X_n\) und die \(\overline X_n\) seien jeweils identisch verteilt, sämtliche Zufallsvariablen seien unabhängig. Die Verteilung von \(Z_n/n\) konvergiere gegen ein Maß auf \([0,1]\). Für \(n\geq n_0\) seien die Verteilungen der \(X_n\) rekursiv gegeben durch \(L(X_n)= L(X_{Z_n-1}+\overline X_{n-Z_n}+n)\). Wir zeigen, daß unter allgemein gehaltenen Voraussetzungen \((X_n- \text{E}X_n)/n\) schwach gegen eine Zufallsvariable \(Y\) konvergiert, deren Verteilung Fixpunkt einer Kontraktion ist. Man erhält daraus die Abschätzung \[ \text{P}(|X_n- \text{E}X_n|\geq\varepsilon \text{E}X_n)\leq\text{Const }n^{-2\varepsilon}. \] Bei der zur Herleitung des Resultates durchgeführten Untersuchung der Erwartungswerte \(\text{E}X_n\) erhalten wir ein weiteres allgemeines Resultat: Sei \(\{\mu_n\}_{n\geq n_0}\) eine Folge von Wahrscheinlichkeitsmaßen jeweils auf der Menge \(\{1/n,2/n,\dots,(n-1)/n\}\), die schwach gegen ein Wahrscheinlichkeitsmaß \(\mu\) auf \([0,1]\) konvergiert. Weiter seien \(a\) und \(c\) Funktionen von \(\mathbb{N}\) nach \(\mathbb{R}\), und für \(n\geq n_0\) gelte die Rekursionsgleichung \(a(n)= \sum^{n-1}_{n=1}\mu_n(k/n)a(k)+ c(n)\). Wir zeigen: Ist \(c\) von beschränkter Variation und \(\int^\infty_{n_0} c(s)/s ds=\infty\), so gilt \(a(n)\cong\text{const }\int^n_{n_0} c(s)/s ds\), ist \(|c|\) monoton fallend und \(\int^\infty_{n_0}|c(s)|/s ds\) endlich, so existiert \(\lim a(n)\) und ist endlich. Zum Beweis dieses Ergebnisses konstruieren wir einen speziellen Markov-Prozeß und verwenden Ergebnisse aus der Erneuerungstheorie. Unter gewissen Voraussetzungen gilt es in der Literatur als gesichert, daß für alle Quicksort-Varianten \(\text{E}X_n=\text{const }n\ln n+\text{rest}(n)\), mit \(\text{rest}(n)/n\), beschränkt, gilt. Wir geben eine Variante an, für die unser Resultat \(\text{rest}(n)/n\to\infty\) liefert.
- A limit theorem for “quicksort”
- Asymptotic distributions for random median quicksort
- On a multivariate contraction method for random recursive structures with applications to quicksort
- How Many Comparisons Does Quicksort Use?
- Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
- On the analysis of stochastic divide and conquer algorithms
- Asymptotic distributions for random median quicksort
- Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
- Stochastic analysis of the Merge-Sort algorithm
- scientific article; zbMATH DE number 870696 (Why is no real title available?)
- Using nonlinear difference equations to study Quicksort algorithms
- All solutions of the stochastic fixed point equation of the Quicksort process
- On the (k, r)-Quicksort on the fly process
- The total path length of split trees
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4349938)