Interval algorithm for random number generation (Q4340328)

Zu einer vorgegebenen Verteilung \(\{q_1,\dots, q_N\}\) für Zufallswerte \(X\) aus \(\{1,\dots,N\}\) wird ein Zufallsbaum betrachtet: Jeder Knoten hat \(M\) Zweige oder ist Endknoten mit einem der möglichen Werte \(X\), und zwar so, daß jede von \(K\) Zufallsfolgen \((Z_{ik})\) mit \(Z\) aus \(\{1,\dots,M\}\) und Wahrscheinlichkeit \((p_1,\dots,p_M)\) einen Weg \(k\) (über jeweils Zweig \(Z_{ik}\) vom \(i\)-ten Knoten) liefert zu einem Endknoten mit Wert \(X_k\) mit Wahrscheinlichkeit \(q_k\). Das beschriebene Verfahren ``Intervall-Algorithmus'' liefert implizit die Lage der Endknoten in einem solchen Baum. Dabei sind Schranken und Optimal-Aussagen für die zu erwartende Anzahl der benötigten \(Z_{ik}\) (= Länge der Wege) angegeben, und zwar für beliebige Verteilungen \((p_m)\) und \((q_n)\) und für Sonderfälle. Gewünscht sind: Genau \(K\) \(X\)-Werte. Unbestimmt viele \(X\). \(X\) wie aus einem Markov-Prozeß stammend. \(Z\) aus einem Markov-Prozeß vorgegeben. Ein tiefgreifender Literatur-Nachweis sichert die Ergebnisse.