Paper by Martin L. 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

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.

Availability:

The paper is available in PDF (1406k).

See information on file formats.

[Google Scholar search]