Yet another application of a binomial recurrence. Order statistics

DOI10.1007/BF02241658zbMath0686.62008OpenAlexW1488981024MaRDI QIDQ1262639

Vernon Rego, Wojciech Szpankowski

Publication date: 1990

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02241658

zbMATH Keywords

order statisticsalternating sumrecursive expressionprogram unificationaccurate asymptotic expressionsbinomial recurrenceconcurrency enhancementi.i.d. geometric random variablesmoments of the maximum

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Exact distribution theory in statistics (62E15) Order statistics; empirical distribution functions (62G30) Probabilistic methods, stochastic differential equations (65C99)

Related Items (18)

The binomial transform and the analysis of skip lists ⋮ Binary search trees constructed from nondistinct keys with/without specified probabilities ⋮ The number of distinct values in a geometrically distributed sample ⋮ The Largest Missing Value in a Sample of Geometric Random Variables ⋮ Epidemic Automaton and the Eden Model: Various Aspects of Robustness ⋮ Combinatorics of geometrically distributed random variables: Left-to-right maxima ⋮ On descents after maximal values in samples of discrete random variables ⋮ The binomial transform and its application to the analysis of skip lists ⋮ Consecutive records in geometrically distributed words ⋮ Randomized registers and iterative algorithms ⋮ Value and position of large weak left-to-right maxima for samples of geometrically distributed variables ⋮ On the expectation of the maximum of IID geometric random variables ⋮ The Maximum of Independent Geometric Random Variables as the Time for Genomic Evolution ⋮ From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader ⋮ How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems ⋮ The average position of the \(d\)th maximum in a sample of geometric random variables ⋮ A result in order statistics related to probabilistic counting ⋮ Descents following maximal values in samples of geometric random variables

Cites Work

• The evaluation of an alternative sum with applications to the analysis of some data structures
• On a recurrence equation arising in the analysis of conflict resolution algorithms
• Some results on V-ary asymmetric tries
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Yet another application of a binomial recurrence. Order statistics