(Warning, **equation-heavy** post!)

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

We have groups of agents, each of equal size (lets say . Positions of groups are indexed: . Groups ,,diffuse”, and they diffuse at different speeds, depending on the position of the group:

(where is the amount of agents disappearing from group being at position 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:

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

For example, if :

(1 unit of time)

( units of time)

( units of time)

and the answer is

Continue reading