chung@cps.msu.EDU (Moon Jung Chung) (02/09/91)
Does anyone know how to solve the following problem ? Let X(n) and Y(n) be random variables. A random variable Z(n+1) is defined : Z(n+1) = max [ X(n) , Y(n) ] + U, where U, X(0), Y(0) are random variables of exponential distribution with mean lambda, and X(n) and Y(n) are random variables following the distribution Z(n). This problem arises in the following case : Suppose that we have a tennis tournament of N=2**n players. There are enough courts to hold N/2 matches at the same time. The schedule of the matches is fixed except the time. The duration of each game is a random variable, (for example, following exponential distribution). As soon as a game is over, the winner advances to the next game. For each match, if both players are available, the match starts immediately. The question is how long will it take to finish the tournament? We can also modify the problem such that it takes a time to go from one court to another court (for the next game). If this time is random variable with uniform distribution of [0,m], how long will it take to finish the tournament? Can we obtain an approximate solution? ---Moon Jung Chung (chung@cpswh.cps.msu.edu) Department of Computer Science MSU