The forgetfulness of balls and bins |
| |
Authors: | Will Perkins |
| |
Institution: | School of Mathematics, Georgia Institute of Technology, Atlanta, GA |
| |
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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 |
| |
Keywords: | balls‐and‐bins planted distributions detection random structures |
|
|