کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868501 | 1439978 | 2018 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Pachinko
ترجمه فارسی عنوان
پچینکو
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پچینکو، توزیع احتمالات،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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(nk2) pins, which is close to the information-theoretic lower bound of Ω(nk).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 226-242
Journal: Computational Geometry - Volume 68, March 2018, Pages 226-242
نویسندگان
Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Ferran Hurtado, Jason S. Ku, Jayson Lynch,