Experimental Evaluation of the Height of a Random Set of Points in a d-Dimensional Cube

摘要

We develop computationally feasible algorithms to numerically investigate the asymptotic behavior of the length H_d(n) of a maximal chain (longest totally ordered subset) of a set of n points drawn from a uniform distribution on the d-dimensional unit cube V_d = [0, l]~d. For d ≥ 2, it is known that c_d(n) = H_d(n)~(1/d) converges in probability to a constant c_d < e, with lim_d→∞ c_d = e. For d = 2, the problem has been extensively studied, and, it is known that c_2 = 2. Monte Carlo simulations coupled with the standard dynamic programming algorithm for obtaining the length of a maximal chain do not yield computationally feasible experiments. We show that H_d(n) can be estimated by considering only the chains that are close to the diagonal of the cube and develop efficient algorithms for obtaining the maximal chain in this region of the cube. We use the improved algorithm together with a linearity conjecture regarding the asymptotic behavior of c_d(n) to obtain even faster convergence to c_d. We present experimental simulations to demonstrate our results and produce new estimates of c_d for d ∈ {3,..., 6}.