In this paper, we study random minimax trees of the incremental type. These are complete b-ary trees with n levels of edges, in which we associate independent identically distributed random variables with the edges. The value of a leaf is the sum of the edge values on the path to the root. The value of each internal node is obtained at alternating levels by taking the minimum or maximum value of the values of the children. We are interested in the behavior of the value of the root, V_n. For bounded generic edge random variable X, we show that V_n / n tends to a limit almost surely as n \to \infty. The limit is a highly nonlinear function of the distribution of X. For the case of a Bernoulli random variable withparameter p, the limit is a continuous function that is zero for p near zero, one for p near one, 1/2 for p in an interval around 1/2, and nonlinear inbetween. A comparison is made with a random minimax tree model studied by Pearl, in which the leaf values are independent.


Back to Random Discrete Structures Table of Contents