Tag Archives: generating function

Asymptotics and generating functions

(Warning, equation-heavy post!)

A while ago I stumbled upon a following problem (when doing analysis of a certain distributed exploration algorithm):

We have n groups of agents, each of equal size (lets say =1. Positions of groups are indexed: 1, 2,\ldots,n. Groups ,,diffuse”, and they diffuse at different speeds, depending on the position of the group:
\lambda_i = \frac{1}{i}
(where \lambda_i is the amount of agents disappearing from group being at position i in one unit of time)

Whenever a group size is reduced to 0, (it will be always a first group), every other one is shifted:
2 \to 1, 3 \to 2, \ldots, n \to (n-1)
[0,a_2,a_3,\ldots,a_n] \text{ into} [a_2,a_3,\ldots,a_n]

Question: How long does it take to dissipate all the groups? (We are not interested in exact formula, just asymptotic one.)

For example, if n=3:
[1,1,1] \to [0,\frac{1}{2},\frac{2}{3}]
(1 unit of time)
[\frac{1}{2},\frac{2}{3}] \to [0,\frac{5}{12}]
(\frac{1}{2} units of time)
[\frac{5}{12}] \to [0]
(\frac{5}{12} units of time)
and the answer is 1 + \frac{1}{2} + \frac{5}{12} = \frac{23}{12}
Continue reading