Paper by Erik D. Demaine

Reference:

Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Ferran Hurtado, Jason S. Ku, and Jayson Lynch, “Pachinko”, Computational Geometry: Theory and Applications, volume 68, March 2018, pages 226–242. In memory of our friend Ferran Hurtado

BibTeX

@Article{Pachinko_CGTA,
  AUTHOR        = {Hugo A. Akitaya and Erik D. Demaine and Martin L. Demaine and Adam Hesterberg and Ferran Hurtado and Jason S. Ku and Jayson Lynch},
  TITLE         = {Pachinko},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 68,
  MONTH         = {March},
  YEAR          = 2018,
  PAGES         = {226--242},
  NOTE          = {In memory of our friend Ferran Hurtado},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2017.06.011},
  dblp          = {https://dblp.org/rec/journals/comgeo/AkitayaDDHHKL18},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.comgeo.2017.06.011">ScienceDirect</A> and as <A HREF="https://arXiv.org/abs/1601.05706">arXiv:1601.05706</A>.},
}

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²) pins, which is close to the information-theoretic lower bound of Ω(n k).

Comments:

This paper is also available from ScienceDirect and as arXiv:1601.05706.

Availability:

The paper is available in PDF (1406k).

See information on file formats.

[Google Scholar search]