Journal of the Iranian Statistical Society
http://jirss@irstat.ir
Journal of The Iranian Statistical Society - Journal articles for year 2004, Volume 3, Number 2Yektaweb Collection - http://www.yektaweb.comen2004/11/11Connecting Yule Process, Bisection and Binary Search Tree via Martingales
http://jirss.irstat.ir/browse.php?a_id=104&sid=1&slc_lang=en
We present new links between some remarkable martingales found in the study of the Binary Search Tree or of the bisection problem, looking at them on the probability space of a continuous time binary branching process.
Brigitte ChauvinProfile and Height of Random Binary Search Trees
http://jirss.irstat.ir/browse.php?a_id=107&sid=1&slc_lang=en
The purpose of this article is to survey recent results on distributional properties of random binary search trees. In particular we consider the profile and the height.
Michael DrmotaCompact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth
http://jirss.irstat.ir/browse.php?a_id=108&sid=1&slc_lang=en
Suffix trees are the most frequently used data structures in algorithms on words. In this paper, we consider the depth of a compact suffix tree, also known as the PAT tree, under some simple probabilistic assumptions. For a biased memoryless source, we prove that the limiting distribution for the depth in a PAT tree is the same as the limiting distribution for the depth in a PATRICIA trie, even though the PATRICIA trie is constructed from statistically independent strings. As a result, we show that the limiting distribution for the depth in a PAT tree built over n suffixes is normal.
Philippe JacquetOne-Sided Interval Trees
http://jirss.irstat.ir/browse.php?a_id=109&sid=1&slc_lang=en
We give an alternative treatment and extension of some results of Itoh and Mahmoud on one-sided interval trees. The proofs are based on renewal theory, including a case with mixed multiplicative and additive renewals.
Svante JansonP´olya-Type Urn Models with Multiple Drawings
http://jirss.irstat.ir/browse.php?a_id=115&sid=1&slc_lang=en
We investigate the distribution, mean value, variance and some limiting properties of an urn model of white and red balls under random multiple drawing (either with or without replacement) when the number of white and red balls added follows a schedule that depends on the number of white balls chosen in each drawing.
Norman JohnsonOn the Average Height of b-Balanced Ordered Trees
http://jirss.irstat.ir/browse.php?a_id=110&sid=1&slc_lang=en
An ordered tree with height h is b-balanced if all its leaves have a level l with h − b <= l <= h, where at least one leaf has a level equal to h − b. For large n, we shall compute asymptotic equivalents to the number of all b-balanced ordered trees with n nodes and of all such trees with height h. Furthermore, assuming that all b-balanced ordered trees with n nodes are equally likely, we shall determine the exact asymptotic behaviour of the average height of such a tree together with the variance.
Rainer KempMeasuring Post–Quickselect Disorder
http://jirss.irstat.ir/browse.php?a_id=111&sid=1&slc_lang=en
This paper deals with the amount of disorder that is left in a permutation after one of its elements has been selected with quickselect with or without median-of-three pivoting. Five measures of disorder are considered: inversions, cycles of length less than or equal to some m, cycles of any length, expected cycle length, and the distance to the identity permutation. “Grand averages” for each measure of disorder for a permutation after one of its elements has been selected with quickselect, where 1, 2, . . . , n are the elements being permuted, are computed, as well as more specific results.
Alois PanholzerPeriodic Oscillations in the Analysis of Algorithms and Their Cancellations
http://jirss.irstat.ir/browse.php?a_id=112&sid=1&slc_lang=en
A large number of results in analysis of algorithms contain fluctuations. A typical result might read “The expected number of . . . for large n behaves like log2 n + constant + delta(log2 n), where delta(x) is a periodic function of period one and mean zero.” Examples include various trie parameters, approximate counting, probabilistic counting, radix exchange sort, leader election, skip lists, adaptive sampling. Often, there are huge cancellations to be noted, especially if one wants to compute variances. In order to see this, one needs identities for the Fourier coefficients of the periodic functions involved. There are several methods to derive such identities, which belong to the realm of modular functions. The most flexible method seems to be the calculus of residues. In some situations, Mellin transforms help. Often, known identities can be employed. This survey shows the various techniques by elaborating on the most important examples from the literature.
Helmut ProdingerQUICKSELECT Revisited
http://jirss.irstat.ir/browse.php?a_id=113&sid=1&slc_lang=en
We give an overview of the running time analysis of the random divide-and-conquer algorithm FIND or QUICKSELECT. The results concern moments, distribution of FIND’s running time, the limiting distribution, a stochastic bound and the key: a stochastic fixed point equation.
Uwe R¨oslerProbability Generating Functions for Sattolo’s Algorithm
http://jirss.irstat.ir/browse.php?a_id=114&sid=1&slc_lang=en
In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently, H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger’s analysis by finding limit laws for the same two random variables.<br>The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results by determining the “grand” probability generating functions of the random variables.<br>The focus throughout is on using standard methods that give a unified approach, and open the door to further study
Mark C. Wilson