(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
A good observation is that instead of operating on finite size lists, we can start with infinite one:
If we name leading terms of the consecutive steps:
(so is a time between total dissipation of th and th groups):
Above can be rewritten to:
With a little bit of guessing and numerology, I found following solution:
So, (for )
and our answer is:
But, I dislike being forced to guess..
The operation we did previously, really closely resembles multiplication of polynomials.
If we write the generating functions:
then, not surprising:
And bam! We got our terms here.
So our original constraints could be written:
and by integrating both sides:
so our constraint is:
so our original problem reduces to finding asymptotic of th term of:
Is there a theory connecting asymptotic of terms of sequences with generating functions?
What we found is that:
(we can skip from nominator,as it is just shift by one)
what if I want to closed formula, for, lets say:
(by writing I mean the fact that exact sum probably doesn’t have finite representation
as an elementary function, so we allow to change the terms by finite multiplier to make the resulting function ,,nice”)
or asymptotic behavior of terms of
So, I would appreciate any help with this problem.