• search hit 1 of 3
Back to Result List

## On the Accuracy of Loader's Algorithm for the Binomial Density and Algorithms for Rectangle Probabilities for Markov Increments

### Über die Genauigkeit von Loaders Algorithmus für die Binomialdichte und Algorithmen für Rechteckwahrscheinlichkeiten für Markov-Inkremente

• The main achievement of this thesis is an analysis of the accuracy of computations with Loader's algorithm for the binomial density. This analysis in later progress of work could be used for a theorem about the numerical accuracy of algorithms that compute rectangle probabilities for scan statistics of a multinomially distributed random variable. An example that shall illustrate the practical use of probabilities for scan statistics is the following, which arises in epidemiology: Let n patients arrive at a clinic in d = 365 days, each of the patients with probability 1/d at each of these d days and all patients independently from each other. The knowledge of the probability, that there exist 3 adjacent days, in which together more than k patients arrive, helps deciding, after observing data, if there is a cluster which we would not suspect to have occurred randomly but for which we suspect there must be a reason. Formally, this epidemiological example can be described by a multinomial model. As multinomially distributed random variables are examples of Markov increments, which is a fact already used implicitly by Corrado (2011) to compute the distribution function of the multinomial maximum, we can use a generalized version of Corrado's Algorithm to compute the probability described in our example. To compute its result, the algorithm for rectangle probabilities for Markov increments always uses transition probabilities of the corresponding Markov Chain. In the multinomial case, the transition probabilities of the corresponding Markov Chain are binomial probabilities. Therefore, we start an analysis of accuracy of Loader's algorithm for the binomial density, which for example the statistical software R uses. With the help of accuracy bounds for the binomial density we would be able to derive accuracy bounds for the computation of rectangle probabilities for scan statistics of multinomially distributed random variables. To figure out how sharp derived accuracy bounds are, in examples these can be compared to rigorous upper bounds and rigorous lower bounds which we obtain by interval-arithmetical computations.
• In dieser Arbeit wird in Verallgemeinerung von Corrado (2011) ein Algorithmus hergeleitet, welcher die Berechnung von Rechteckwahrscheinlichkeiten für Markov-Inkremente ermöglicht. Es wird gezeigt, dass es sich bei multinomialverteilten und bei multivariat hypergeometrisch verteilten Zufallsgrössen um Markov-Inkremente handelt. In einem Beispiel wird gezeigt, dass der hergeleitete Algorithmus im Multinomialfall schneller ein Ergebnis liefert, als eine herkömmliche Methode, bei welcher alle Elemente des Trägers der Multinomialverteilung konstruiert werden und deren relevante Einpunktwahrscheinlichkeiten aufsummiert. Als Anwendung des hergeleiteten Algorithmus wird eine Verteilung der Spannweite einer multinomial verteilten Zufallsgrössen berechnet. Für die Untersuchung der Rechengenauigkeit bei dem hergeleiteten Algorithmus ist es im Multinomialfall nötig, zunächst die Genauigkeit eines Algorithmus zu untersuchen, welcher Einpunktwahrscheinlichkeiten von Binomialverteilungen berechnet. Dies geschieht bei dem Statistik Softwarepaket R mit einem Algorithmus nach Loader. Daher werden Hilfsresultate hergeleitet, welche dazu dienen können, einen Satz über die Rechengenauigkeit des Algorithmus nach Loader herzuleiten. Zudem werden in Beispielen die Genauigkeit des hergeleiteten Algorithmus im Multinomialfall sowie im multivariat hypergeometrischen Fall untersucht mit Hilfe von intervallarithmetischen Berechnungen. Es wird folgendes statistische Anwendungsbeispiel untersucht: Es kommen n Patienten in einer Klinik an d=365 Tagen des Jahres an, jeder der Patienten mit Wahrscheinlichkeit 1/d an jedem dieser d Tage und alle Patienten unabhängig voneinander. Wie gross ist die Wahrscheinlichkeit, dass 3 aufeinanderfolgende Tage existieren, an denen zusammen mehr als k Patienten ankommen?