Pachinko

DOI10.1016/J.COMGEO.2017.06.011MaRDI QIDQ1699294zbMATH OpenOpenAlexFDO

Authors Hugo A. Akitaya, Martin L. Demaine, Adam Hesterberg, Ferran Hurtado, Jason S. Ku, Jayson Lynch, Erik D. Demaine

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.05706, https://hdl.handle.net/1721.1/128438

zbMATH Keywords

probability distributionsPachinko

Mathematics Subject Classification ID

Graph theory (05C99)

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(nk)$.

Recommendations

• Uniform distribution on Pachinko
• Uniform distribution for Pachinko
• Deterministic analysis of the probability machine
• scientific article; zbMATH DE number 2164131
• Binomial bowling

Cites work

• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Planar graphs, via well-orderly maps and trees

Cited in

(4)

• Deterministic analysis of the probability machine
• Binomial bowling
• Uniform distribution for Pachinko
• Uniform distribution on Pachinko

This page was built for publication: Pachinko

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