Suppose we have n objects, each with a 1/m chance of disappearing in any given second. What is the mean of the number of seconds until all of them are gone? This may seem like a well-posed question, but it's actually ambiguous, because it doesn't clearly specify whether "1/m per second" is to be applied continuously as a constant rate, discontinuously on a sequence of discrete 1-second intervals, or as any of an infinite number of other distributions yielding a 1/m chance of disappearing in any given second (not to mention the ambiguity in the conditional, i.e., an object could have a uniform probability of exactly 1/m during each of m intervals). If we're looking for an exact answer, the precise interpretation of the "rate" is important. The continuous constant-rate interpretation is easiest to solve, and can be viewed as a linear Markov chain with n+1 states, where the initial state has all n objects present, the next state has n-1 objects present, and so on. The transition from the state with k objects to the next state has a constant exponential rate of k(1/m), and therefore a mean transition time of m/k. The mean transition time of the initial state with k=n down to the empty state with k=0 is just the sum of the individual mean transition times, which is m (1 + 1/2 + 1/3 + 1/4 + ... + 1/n) The purely discrete interpretation leads to a somewhat more complicated problem (as usual). Each individual object has a probability of 1.0 of being present at the beginning of the first 1-second interval, and a probability of (m-1)/m of being present at the end of the first interval. In general, each object has a probability of [(m-1)/m]^k of being present at the end of the kth interval, and so it's probability of NOT being present at the end of the kth interval is simply the complement of this value, i.e., 1 - [(m-1)/m]^k. It follows that the probability of ALL n objects being gone at the end of the kth interval is the product of their individual probabilities of being gone, so it is given by {1 - [(m-1)/m]^k}^n. Of course, this is the cumulative probability, which approaches 1.0 as k increases, but we need to know the probability of the system entering this "empty state" during the kth second. Thus we need to subtract the probability of being in the empty state at the end of the (k-1)th state. This gives us the probability of entering the "empty state" during the kth discrete 1-second interval: P{k} = {1 - [(m-1)/m]^k}^n - {1 - [(m-1)/m]^(k-1)}^n The mean number of intervals required to reach the empty state is then given by the weighted sum inf k_mean = SUM k P{k} k=1 For small values of n we can just algebraically expand the expression for P{k} into a sum of powers of (m-1)/m, and then determine the closed-form expression for the infinite sum of powers. However, for large values of n this becomes tedious, and it may be best to simply compute the sum directly - or approximate it by the continuous exponential solution given above. Here's a little table of k_mean for n objects with 1/m chance of disappearing during each discrete 1-second interval: m --------------------------------------------- n 1 2 3 4 5 --- ----- ------- ------- ---------- ---------- 1 1 2 3 4 5 2 1 8/3 21/5 40/7 65/9 3 1 22/7 477/95 1780/259 1595/183 4 1 368/105 6963/1235 50128/6475 221405/22509 The difference between the continuous and discrete interpretations can be seen by comparing the answers for 4 objects that each have a probability of 1/5 of disappearing during each second (on the condition that they haven't already disappeared). The solution for the discrete interpretation is k_mean = 221405/22509 = 9.836287 sec whereas the solution for the continuous-rate interpretation is k_mean = 5 [ 1 + 1/2 + 1/3 + 1/4 ] = 125/12 = 10.416666 sec so they differ by 0.58 seconds, nearly 6%. Incidentally, we can simplify the formula inf k_mean = SUM k [ (1 - r^k)^n - (1 - r^(k-1))^n ] k=1 where r = (m-1)/m, by noting that the first few terms of the summation are 1(1 - r^1)^n - 1(1 - r^0)^n + 2(1 - r^2)^n - 2(1 - r^1)^n + 3(1 - r^3)^n - 3(1 - r^2)^n + etc. Taking advantage of the cancellation on consecutive terms, we can express the sum of the first t terms as t-1 t(1 - r^t)^n - SUM (1 - r^k)^n k=1 Adding and subtracting t-1, this can be written as t-1 t(1 - r^t)^n - (t-1) + SUM (1 - (1 - r^k)^n) k=1 In the limit as t goes to infinity the two leading terms go to 1 (because r^t goes to zero), so we are left with the result inf k_mean = 1 + SUM (1 - (1 - r^k)^n) k=1 Noting that the summand would be 1 with k=0, we can bring the 1 inside the summation and write inf k_mean = SUM (1 - (1 - r^k)^n) k=0 This is confirmed by considering the simple case when n=1, for which we know the mean survival time is just m. In this case the summand in the preceeding formula reduces to r^k, so by the geometric series we have the sum 1/(1-r) = m. In the same way we can easily derive simple closed-form expressions for small values of n. For example, if n=2 the summand reduces to 2r^k - (r^2)^k, and so the infinite sum is 2/(1-r) - 1/(1-r^2), which equals m(3m-2)/(2m-1). In general, for any fixed n, we have the closed-form expression C(n,1) C(n,2) C(n,n) k_mean[n] = -------- - -------- + ... -(-1)^n -------- 1 - r^1 1 - r^2 1 - r^n where C(i,j) is the binomial coefficient. For example, with n=5 we have 5 10 10 5 1 k_mean[5] = ----- - ------- + ------- - ------- + ------- 1 - r 1 - r^2 1 - r^3 1 - r^4 1 - r^5 In terms of m this can be written in the form k_mean[5] = / 10m 10m^2 5m^3 m^4 \ m( 5 - ---- + --------- - -------------- + -------------------- ) \ 2m-1 3m^2-3m+1 4m^3-6m^2+4m-1 5m^4-10m^3+10m^2-5m+1 / It's interesting that for sufficiently large m (meaning a LOW rate of disappearance) we can neglect all but the leading term in each denominator, and so the expression reduces to / 10 10 5 1 \ m( 5 - ---- + ---- - --- + --- ) \ 2 3 4 5 / which, not surprisingly, is exactly equal to to solution for the case of a constant exponential rate / 1 1 1 1 \ m( 1 + --- + --- + --- + --- ) \ 2 3 4 5 / Thus we're led to the nice little combinatorial identity n 1 n -C(n,k) SUM --- = SUM (-1)^k -------- k=1 k k=1 k

Return to MathPages Main Menu