Eigen-distribution on assignments for game trees with random properties
Chenguang Liu, Kazuyuki Tanaka · 2007
In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree Tk2 with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In ID setting, we prove that the distributional probability ϱ belongs to [EQUATION] and ϱ is a strictly increasing function on rounds [EQUATION]. In CD setting, we propose a reverse assigning technique (RAT) to form 1-set and 0-set, then show that E1-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.