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}$