Birthday paradox, coupon collectors, caching algorithms and self- organizing search

DOI10.1016/0166-218X(92)90177-CzbMath0762.60006OpenAlexW2005830269WikidataQ29041606 ScholiaQ29041606MaRDI QIDQ1201808

Loÿs Thimonier, Philippe Flajolet, Daniéle Gardy

Publication date: 17 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90177-c

zbMATH Keywords

integral representations coupon collector problem random allocation processes

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Related Items

A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space, The Chebotarev Invariant of a Finite Group, On the resilience of Even-Mansour to invariant permutations, The move-to-partner rule for self-organizing task allocation on a linear array, The self-power map and collecting all residue classes, \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm, Analytic combinatorics for computing seeding probabilities, Data Collection in Population Protocols with Non-uniformly Random Scheduler, Occupancy urn models in the analysis of algorithms, On Ramanujan's $Q$-function, Laplacian versus adjacency matrix in quantum walk search, Optimization results for a generalized coupon collector problem, On the distribution of the search cost for the move-to-front rule with random weights, Some upper and lower bounds on the coupon collector problem, A Transposition Rule Analysis Based on a Particle Process, Information Transmission under Random Emission Constraints, Measures of distinctness for random partitions and compositions of an integer, The Weighted Coupon Collector’s Problem and Applications, Application of Smirnov words to waiting time distributions of runs, General asymptotic estimates for the coupon collector problem, On determining the congruence of point sets in $d$ dimensions, Non-redundant random generation algorithms for weighted context-free grammars, New Results on a Generalized Coupon Collector Problem Using Markov Chains, A Model for Birdwatching and other Chronological Sampling Activities, Packing returning secretaries, Philippe Flajolet's early work in combinatorics, The logarithmic Zipf law in a general urn problem, A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees, Local limit theorems for finite and infinite urn models, On a cover time problem on a dynamic graph with steps at random times, Birth, death, coincidences and occupancies: solutions and applications of generalized birthday and occupancy problems, Coevolution of collective opinions and actions under two different control inputs, A non-uniform birthday problem with applications to discrete logarithms, A quantitative study of pure parallel processes, Stopping Rules in Balanced Allocation Problems: Exact and Asymptotic Distributions, On the number of driver nodes for controlling a Boolean network when the targets are restricted to attractors, A Collector's Problem with Renewal Arrival Processes, Divisibility properties of random samples of integers, Running time analysis of broadcast consensus protocols, Limits and rates of convergence for the distribution of search cost under the move-to-front rule, Minimum Expected *-Cast Time in DTNs, Limiting search cost distribution for the move-to-front rule with random request probabilities, The limiting move-to-front search-cost in law of large numbers asymptotic regimes, Least-recently-used caching with dependent requests, Uniform asymptotics of some Abel sums arising in coding theory, SIZE-BIASED PERMUTATION OF DIRICHLET PARTITIONS AND SEARCH-COST DISTRIBUTION, Uniform versus Zipf distribution in a mixing collection process, Sampling Formulae Arising from Random Dirichlet Populations, Critical sizing of LRU caches with dependent requests, Unnamed Item, Unnamed Item, A fluid limit for a cache algorithm with general request processes, Data collection in population protocols with non-uniformly random scheduler, The general birthday problem, Monte Carlo cubature construction, Coupon collector's problem with unlike probabilities, Methods for Studying Generalized Birthday and Coupon Collection Problems, Threshold-based network structural dynamics, ORIGAMI: A Novel and Effective Approach for Mining Representative Orthogonal Graph Patterns, Computing absorbing times via fluid approximations, Markov chains, ${\mathscr R}$-trivial monoids and representation theory, Asymptotics for the random coupon collector problem, Speed and concentration of the covering time for structured coupon collectors, Finding shuffle words that represent optimal scheduling of shared memory access, Mixing times for a constrained Ising process on the two-dimensional torus at low density, Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities, On the Maximum–Minimums Identity: Extension and Applications, Maximum of exponential random variables, Hurwitz's zeta function, and the partition function, Analytical results for the distribution of first hitting times of random walks on random regular graphs, The Coupon Collector's Problem Revisited: Asymptotics of the Variance

Cites Work