Uniform distribution for Pachinko
Uniform distribution for Pachinko
复制标题
弹珠机均匀分布
DOI：
10.1016/j.tcs.2020.05.032
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Naoki Kitamura,Yuya Kawabata Yuya,Taisuke Izumi
中科院分区：
文献类型：
--
作者：
Ryota Eguchi;Naoki Kitamura;Taisuke Izumi;Naoki Kitamura,Yuya Kawabata Yuya,Taisuke Izumi
弹球盘是一种类似于弹球的日本机械赌博游戏。近年来，人们提出了几种柏青哥的数学模型。一块地里钉了许多大头针。一个球从操场的顶部掉下来，球福尔斯掉了下来。在50-50模型中，如果球击中一个大头针，它以相等的概率移动到大头针的左侧或右侧通道。针的布置生成所有列的丢弃概率的分布。这个问题被认为是通过产生均匀分布。以前的研究已经证明了（1/2 a）-均匀分布对于a∈{0，1，2，3，4}是可能的，并且证明了对于任何正整数a都是可能的。本文给出了这一猜想的构造性证明。本研究还正式提出了一个自然的决策问题，该模型产生的，同时调查其计算复杂性。更确切地说，给定任何跌落概率分布A和任何部分跌落概率分布B，本研究使用非确定性多项式时间（NP）硬度来确定是否存在将A转换为B的引脚排列。
Pachinko is a Japanese mechanical gambling game similar to pinball. Recently, several mathematical models of Pachinko have been proposed. A number of pins are spiked in a field. A ball drops from the top of the playfield and the ball falls down. In the 50-50 model, if the ball hits a pin, it moves to the left or right passage of the pin with an equal probability. An arrangement of pins generates a distribution of the drop probability for all of the columns. This problem was considered by generating uniform distributions. Previous studies have demonstrated that the (1/2 a)-uniform distribution is possible for a∈{0, 1, 2, 3, 4} and is conjectured so that it is possible for any positive integer a. This study describes the constructive proof for this conjecture. This study also formalizes a natural decision problem yielded by this model while investigating its computational complexity. More precisely, given any drop-probability distribution A and any partial drop-probability distribution B, this study uses non-deterministic polynomial-time (NP) hardness to determine if there exists a pin arrangement that transforms A into B.