The forgetfulness of balls and bins

DOI10.1002/RSA.20408MaRDI QIDQ4909203zbMATH OpenOpenAlexFDO

Authors Will Perkins

Publication date 12 March 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.5373

zbMATH Keywords

balls-and-binsdetectionplanted distributionsrandom structures

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We find the asymptotic total variation distance between two distributions on configurations of m balls in n labeled bins: in the first, each ball is placed in a bin uniformly at random; in the second, k balls are planted in an arbitrary but fixed arrangement and the remaining m-k balls placed uniformly at random.

Recommendations

• scientific article; zbMATH DE number 1301967
• scientific article; zbMATH DE number 3167451
• scientific article; zbMATH DE number 4003140
• Balls into bins with related random choices
• A short note on the average maximal number of balls in a bin

Cites work

• A Berry-Esseen bound for an occupancy problem
• Expected complexity of graph partitioning problems
• Finding hidden hamiltonian cycles
• Higher criticism for detecting sparse heterogeneous mixtures.
• Normal approximations to sums of scores based on occupancy numbers
• Probability. Theory and examples.
• Why Almost All k-Colorable Graphs Are Easy

Cited in

(1)

• A short note on the average maximal number of balls in a bin

This page was built for publication: The forgetfulness of balls and bins

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909203)