From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: max consecutive runs? Date: 24 Oct 1995 16:14:20 GMT Steve Earth (earther@eskimo.com) wrote: : Suppose you have N balls, x of which are spotted. The balls are drawn out : one at a time (without replacement). What is the expected length of the : largest consecutive run of spotted balls? theodore hwa wrote: >If E(x,N) is the expected value you're looking for, then this recurrence >relation holds: > >E(x,N) = (x/N) + E(x-1, N-1) E(N,0) = 0 Perhaps I misunderstand the question but I disagree. Indeed, E(0,N)=0, but E(1,N)=1 (If there's just one spotted owl, er, ball, then I know just how long the largest run of spotted balls is!). This is not consistent with your formula. I don't know what the pattern is in general, but perhaps I should first clarify what I think the question is. We are considering all N! permutations of the N balls as equally likely, and for each permutation we examine to see what the longest run of spotted balls is. Sum this number over all permutations and divide by N! to get E(x,N). For example, when N=2, you will surely have two runs of length one unless the two spotted balls are adjacent. There are N-1 places where the leftmost (leftmore?) ball can be placed so that the other one is to its right; 2 choices for which spotted ball is on the left; and (N-2)! ways to place the unspotted balls in the open locations of the succession. Thus of the N! permutations, 2*(N-1)! of them have the two spotted balls together, so we have a run of length 2 with probability 2/N and only runs of length 1 otherwise, giving E(2,N) = 1 + 2/N Already for x=3, this argument becomes much more cumbersome, and it looks like it's all downhill from there. You'll have a run of length 3 with probability 6/(N*(N-1)) as in the previous paragraph. To count the permutations with runs of length 2, place a pair and a singleton of spotted balls apart from each other: with the left ball in the pair at position i, the singleton must be between positions i+3 and N: N-i-2 choices; summing over i gives (N-3)(N-2)/2 such arrangements. Double to include cases with the singleton to the left of the pair. Permute the three spotted balls in these slots: multiply by 6. Permute the other balls into the other slots: multiply by (N-3)!. Divide by N! to get the probability, which seems to be 6(N-3)/(N*(N-1)). Now compute expected value: 3*[6/(N*(N-1))] + 2*[6*(N-3)/(N*(N-1))] + + 1*[1 - 6/(N*(N-1)) - 6*(N-3)/(N*(N-1))] so that E(3,N)=1+6/N. At the other extreme we have E(N,N)=N (and of course E(x,N)=0 if x>N). To compute E(N-1,N), note that the one unspotted ball is equally likely to be in any of the N slots, but this has a funny effect on the expected length of the longest (really,"longer") run. With the unspotted ball in position i, the length of the longer run is max(i-1,N-i), so E(N-1,N)=(1/N)(N-1) + (1/N)(N-2) + ... + (1/N)floor(N/2) + ...+(1/N)(N-1) which is E(N-1,N)=(3/4)N - (1/2) - (1/4N) if N is odd E(N-1,N)=(3/4)N - (1/2) if N is even The presence of this parity term makes me loathe to consider other possibilities. I wouldn't be surprised if there are arithmetic errors in my analysis but in any case I think the problem is not pretty. It might be more reasonable to ask for things like lim E(N-x,N)/N as N -> oo with x fixed (or maybe lim E( rN, N)/N with r a fixed ratio). I would not be a person who would know the literature of this kind of problem. I note E(N/2, N) is roughly the expected length of the longest run of Heads when you flip a coin N times. (Not quite -- the present problem assumes the coin is precisely fair: N/2 Heads, N/2 Tails). E(N-2,N) is related to the question of the probabilty that a stick broken into three parts can be reassembled into a triangle. dave