Pachinko

DOI10.1016/J.COMGEO.2017.06.011zbMATH Open1380.05188arXiv1601.05706OpenAlexW4206945263MaRDI QIDQ1699294FDOQ1699294

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)

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

Full work available at URL: https://arxiv.org/abs/1601.05706

Recommendations

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

zbMATH Keywords

probability distributionsPachinko

Mathematics Subject Classification ID

Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)