Name
Abstract | ||
|---|---|---|
Inspired by the Japanese game Pachinko, we study simple (perfectly "inelastic" collisions) dynamics of a unit ball falling amidst point obstacles (pins) in the plane. A classic example is that a checkerboard grid of pins produces the binomial distribution, but what probability distributions result from different pin placements? In the 50-50 model, where the pins form a subset of this grid, not all probability distributions are possible, but surprisingly the uniform distribution is possible for $\{1,2,4,8,16\}$ possible drop locations. Furthermore, every probability distribution can be approximated arbitrarily closely, and every dyadic probability distribution can be divided by a suitable power of $2$ and then constructed exactly (along with extra "junk" outputs). In a more general model, if a ball hits a pin off center, it falls left or right accordingly. Then we prove a universality result: any distribution of $n$ dyadic probabilities, each specified by $k$ bits, can be constructed using $O(n k^2)$ pins, which is close to the information-theoretic lower bound of $\Omega(n k)$. |
Year | Venue | DocType |
|---|---|---|
2018 | Comput. Geom. | Journal |
Volume | Citations | PageRank |
abs/1601.05706 | 0 | 0.34 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hugo A. Akitaya | 1 | 11 | 9.76 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Martin L. Demaine | 3 | 592 | 84.37 |
| Adam Hesterberg | 4 | 4 | 7.07 |
| Ferran Hurtado | 5 | 744 | 86.37 |
| Jason S. Ku | 6 | 0 | 1.01 |
| Jayson Lynch | 7 | 7 | 11.97 |