Eigen-distribution on random assignments for game trees

详细信息    查看全文

• 作者：ChenGuang Liu ; Kazuyuki Tanaka
• 关键词：Eigen-distribution ; Game tree ; Computational complexity ; Distributional complexity ; Randomized algorithms
• 刊名：Information Processing Letters
• 出版年：2007
• 出版时间：16 October 2007
• 年：2007
• 卷：104
• 期：2
• 页码：73-77
• 全文大小：125 K

文摘

In this Letter, we investigate a special distribution, called eigen-distribution, on random assignments for a class of game trees TBFMK-2&_mathId=mml1&_user=10&_cdi=5645&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=f09c6dddfd14f486d26b6923c65ec06b"">. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In the ID case, we prove that the distributional probability belongs to , and is a strictly increasing function on rounds k[1,∞). In the CD case, we propose a reverse assigning technique (RAT) to form two particular sets of assignments, 1-set and 0-set, then show that the E¹-distribution (namely, a particular distribution on the assignments of 1-set such that all the deterministic algorithms have the same complexity) is the unique eigen-distribution for in the global distribution.