<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE ArticleSet PUBLIC "-//NLM//DTD PubMed 2.7//EN" "https://dtd.nlm.nih.gov/ncbi/pubmed/in/PubMed.dtd">
<ArticleSet>
<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>Connecting Yule Process, Bisection and Binary Search Tree via Martingales</ArticleTitle>
<VernacularTitle>مرتبط کردن فرایند یول، دونیم سازی و درخت دودویی از طریق مارتینگلها</VernacularTitle>
			<FirstPage>89</FirstPage>
			<LastPage>116</LastPage>
			<ELocationID EIdType="pii">253617</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Brigitte</FirstName>
					<LastName>Chauvin</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Alain</FirstName>
					<LastName>Rouault</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Binary search tree</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">branching random walk</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">convergence of martingales</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">functional equations</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Yule process</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253617_0b6cb9ea448011bc5e8c079232c5ae47.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>Profile and Height of Random Binary Search Trees</ArticleTitle>
<VernacularTitle>نیم‌رخ و ارتفاع درختهای جستجوی دودویی تصادفی</VernacularTitle>
			<FirstPage>117</FirstPage>
			<LastPage>138</LastPage>
			<ELocationID EIdType="pii">253618</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Michael</FirstName>
					<LastName>Drmota</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Binary search tree</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">generating functions</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Height</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">limiting distribution</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Profile</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253618_cbef1d7f011e1507945ffd826b4a55b7.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth</ArticleTitle>
<VernacularTitle>درختهای پسوند فشرده شبیه ترای‌های ‎ PATRICIA‎ هستند: توزیع حدی ژرفا</VernacularTitle>
			<FirstPage>139</FirstPage>
			<LastPage>148</LastPage>
			<ELocationID EIdType="pii">253619</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Philippe</FirstName>
					<LastName>Jacquet</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Bonita</FirstName>
					<LastName>McVey</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Wojciech</FirstName>
					<LastName>Szpankowski</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Digital trees</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">limiting distribution</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Patricia trie</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">suffix tree</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253619_9901cc05f0b14097b7f90f884a0760b4.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>One-Sided Interval Trees</ArticleTitle>
<VernacularTitle>درختهای بازه‌ای یک طرفه</VernacularTitle>
			<FirstPage>149</FirstPage>
			<LastPage>164</LastPage>
			<ELocationID EIdType="pii">253620</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Svante</FirstName>
					<LastName>Janson</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Car parking</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">interval trees</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">renewal theory</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253620_1f401c84508cc0e77e12bc5645a0cc07.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>P´olya-Type Urn Models with Multiple Drawings</ArticleTitle>
<VernacularTitle>مدلهای آوند پولیاگونه با برداشتهای چندگانه</VernacularTitle>
			<FirstPage>165</FirstPage>
			<LastPage>173</LastPage>
			<ELocationID EIdType="pii">253621</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Norman</FirstName>
					<LastName>Johnson</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Samuel</FirstName>
					<LastName>Kotz</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Hosam</FirstName>
					<LastName>Mahmoud</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Random structure</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Urn model</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253621_8d870a86777c819f792ef43b77e9ff71.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>On the Average Height of b-Balanced Ordered Trees</ArticleTitle>
<VernacularTitle>حثی دربارهٔ ارتفاع متوسط درختهای مرتب b-متعادل</VernacularTitle>
			<FirstPage>175</FirstPage>
			<LastPage>218</LastPage>
			<ELocationID EIdType="pii">253622</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Rainer</FirstName>
					<LastName>Kemp</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>An ordered tree with height h is b-balanced if all its leaves have a level l with h − b</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Asymptotic analysis</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">b-balanced ordered trees</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">enumeration</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">height of trees</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253622_a7c01b13f6d397f2f25a1dda4312b545.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>Measuring Post–Quickselect Disorder</ArticleTitle>
<VernacularTitle>اندازه‌گیری بی‌نظمی پساـ‍زودگزین</VernacularTitle>
			<FirstPage>219</FirstPage>
			<LastPage>249</LastPage>
			<ELocationID EIdType="pii">253623</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Alois</FirstName>
					<LastName>Panholzer</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Helmut</FirstName>
					<LastName>Prodinger</LastName>
<Affiliation></Affiliation>

</Author>
<Author>
					<FirstName>Marko</FirstName>
					<LastName>Riedel</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Cycles</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Disorder</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Inversions</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">permutations</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">quickselect</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253623_4bb7c49b774f4d21408880f3a18d43a5.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>Periodic Oscillations in the Analysis of Algorithms and Their Cancellations</ArticleTitle>
<VernacularTitle>نوسان‌های دوره‌ای در تحلیل الگوریتم‌ها و حذف آنها</VernacularTitle>
			<FirstPage>251</FirstPage>
			<LastPage>270</LastPage>
			<ELocationID EIdType="pii">253624</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Helmut</FirstName>
					<LastName>Prodinger</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Analysis of algorithms</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">approximate counting</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Dedekind’s eta function</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">geometric random variables</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">Mellin transform</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">modular functions</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">periodic oscillations</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">residues</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">tries</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253624_d1038a3c5490b16cdf45ed4af94b5afd.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>QUICKSELECT Revisited</ArticleTitle>
<VernacularTitle>دیداری دیگر با QUICKSELECT</VernacularTitle>
			<FirstPage>271</FirstPage>
			<LastPage>296</LastPage>
			<ELocationID EIdType="pii">253625</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Uwe</FirstName>
					<LastName>R¨osler</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Analysis of algorithms</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">asymptotic distribution</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">FIND</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">FIND process</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">quickselect</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">stochastic algorithm</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">stochastic fixed point equation</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253625_ac7b016964114cbacc81dae27482ca14.pdf</ArchiveCopySource>
</Article>

<Article>
<Journal>
				<PublisherName>Iranian Statistical Society</PublisherName>
				<JournalTitle>Journal of the Iranian Statistical Society</JournalTitle>
				<Issn>1726-4057</Issn>
				<Volume>3</Volume>
				<Issue>2</Issue>
				<PubDate PubStatus="epublish">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</Journal>
<ArticleTitle>Probability Generating Functions for Sattolo’s Algorithm</ArticleTitle>
<VernacularTitle>تابع‌های مولد احتمال برای الگوریتم ساتولو</VernacularTitle>
			<FirstPage>297</FirstPage>
			<LastPage>308</LastPage>
			<ELocationID EIdType="pii">253626</ELocationID>
			
			
			<Language>EN</Language>
<AuthorList>
<Author>
					<FirstName>Mark C.</FirstName>
					<LastName>Wilson</LastName>
<Affiliation></Affiliation>

</Author>
</AuthorList>
				<PublicationType>Journal Article</PublicationType>
			<History>
				<PubDate PubStatus="received">
					<Year>2022</Year>
					<Month>07</Month>
					<Day>23</Day>
				</PubDate>
			</History>
		    <Abstract>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.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 study</Abstract>
		<ObjectList>
			<Object Type="keyword">
			<Param Name="value">Grand PGF</Param>
			</Object>
			<Object Type="keyword">
			<Param Name="value">random cycle generation</Param>
			</Object>
		</ObjectList>
<ArchiveCopySource DocType="pdf">https://jirss.irstat.ir/article_253626_3c2676a3d81ecfbc676a75efa9bafae3.pdf</ArchiveCopySource>
</Article>
</ArticleSet>
