Iranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723Connecting Yule Process, Bisection and Binary Search Tree via Martingalesمرتبط کردن فرایند یول، دونیم سازی و درخت دودویی از طریق مارتینگلها89116253617ENBrigitte ChauvinAlain RouaultJournal Article20220723We 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.https://jirss.irstat.ir/article_253617_5d83190738c87149c4588d576fca5dc6.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723Profile and Height of Random Binary Search Treesنیمرخ و ارتفاع درختهای جستجوی دودویی تصادفی117138253618ENMichael DrmotaJournal Article20220723The 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.https://jirss.irstat.ir/article_253618_4b559a9f2ff7af12225f79f00996151d.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depthدرختهای پسوند فشرده شبیه ترایهای PATRICIA هستند: توزیع حدی ژرفا139148253619ENPhilippe JacquetBonita McVeyWojciech SzpankowskiJournal Article20220723Suffix 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.https://jirss.irstat.ir/article_253619_1f6018dcda590547522d90bff938b9a2.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723One-Sided Interval Treesدرختهای بازهای یک طرفه149164253620ENSvante JansonJournal Article20220723We 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.https://jirss.irstat.ir/article_253620_a50bc13cfe05ff78ee78b6452d339078.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723P´olya-Type Urn Models with Multiple Drawingsمدلهای آوند پولیاگونه با برداشتهای چندگانه165173253621ENNorman JohnsonSamuel KotzHosam MahmoudJournal Article20220723We 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.https://jirss.irstat.ir/article_253621_7f0f99b2d7731a6a3fed555fd227653f.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723On the Average Height of b-Balanced Ordered Treesحثی دربارهٔ ارتفاع متوسط درختهای مرتب b-متعادل175218253622ENRainer KempJournal Article20220723An ordered tree with height h is b-balanced if all its leaves have a level l with h − bhttps://jirss.irstat.ir/article_253622_ad3cfeb268eacdd07e4388953a20648d.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723Measuring Post–Quickselect Disorderاندازهگیری بینظمی پساـزودگزین219249253623ENAlois PanholzerHelmut ProdingerMarko RiedelJournal Article20220723This 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.https://jirss.irstat.ir/article_253623_f8afd5c765c4f72d12fbd915bde8cda2.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723Periodic Oscillations in the Analysis of Algorithms and Their Cancellationsنوسانهای دورهای در تحلیل الگوریتمها و حذف آنها251270253624ENHelmut ProdingerJournal Article20220723A 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.https://jirss.irstat.ir/article_253624_18e1e6689352ed444ef86f31b4b4128d.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723QUICKSELECT Revisitedدیداری دیگر با QUICKSELECT271296253625ENUwe R¨oslerJournal Article20220723We 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.https://jirss.irstat.ir/article_253625_09af6f86248fac806b23d08a1ce5874d.pdfIranian Statistical SocietyJournal of the Iranian Statistical Society1726-40573220220723Probability Generating Functions for Sattolo’s Algorithmتابعهای مولد احتمال برای الگوریتم ساتولو297308253626ENMark C. WilsonJournal Article20220723In 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.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.The focus throughout is on using standard methods that give a unified approach, and open the door to further studyhttps://jirss.irstat.ir/article_253626_bf4528ea90317f1eb0ab9ed3dc58ce16.pdf