No label defined (Q4349938)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1052336
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1052336

      Statements

      0 references
      26 August 1997
      0 references
      stochastic analysis of the quicksort algorithm
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references