# Algorithm to make sequence monotonically increasing by averaging neigbours

Informally: assume one had a sequence $$p_1^{orginal},p_2^{orginal},...,p_n^{orginal}$$ which was monotonically growing, but adding noise you received sequence $$p_1,p_2,...,p_n$$ which may slighly violate monotonicity, we want to average some neigbours getting the new sequence which will be again monotonically growing. What is reasonable algorithm to do it ? The simplest version coming to mind is go througth the list many times and on each pass average pairs of neigbours which violate growth. Something like a bubble sort but with average, not transposition. The hope is that more effective algorithm exists.

For example: consider $$p_1=0.44, p_2= 0.5 ,p_3 =0.3 , p_4= 0.6$$ it is slightly non-motononic because $$p_3 first step: $$p_1^{1} = 0.44, ~p_2^{1} = (0.5+0.3)/2 = 0.4,~ p_3^{1} = 0.6$$ again there is problem: $$p_1^{1}>p_2^1$$, so the second step: $$p_1^{2} = (0.44+0.4)/2=0.42, ~ p_2^{2} = 0.6$$ - the new sequence is monotonically growing.

Detailed: Consider sequence $$p_1=a_1/b_1,p_2 = a_2/b_2, ... p_n=a_n/b_n$$ (where $$0<=p_i <=1$$). We need to split that sequence to subsequnces such that taking averages in each subsequence the new sequnce made of averages will be monotonically growing. What is the algorithm to do it in some reasonably economic way, preferable doing minimal number of averages and maximazing max-min of resulting sequence ?

PS

In fact I need to consider averaging to be $$(a_1+a_2)/(b_1+b_2)$$, not just $$(p_1+p_2)/2$$.

• If $p=a/b$, then also $p=(2a)/(2b)$, and $p=(.73a)/(.73b)$, and $p=(\sqrt2a)/(\sqrt2b)$, so your averaging by mediant is not well-defined. – Gerry Myerson Feb 28 at 22:46
• @GerryMyerson Sorry I was slightly impresise, I have not only p, but concrete a, b. So it is well defined. – Alexander Chervov Mar 1 at 4:11
• But I think both questions should have the same idea of solution if any exists ( better than straightforward) – Alexander Chervov Mar 1 at 4:25
• What exactly are you looking for? A faster algorithm, or a more precise one? In the latter case the answer will depend on the measure of the error (least squares?) and the form and size of the noise. – Jan-Christoph Schlage-Puchta Mar 2 at 11:50
• @Jan-ChristophSchlage-Puchta I would be happy for any ideas. The first thing I do not see how to speed up. The second I am worried about uniqueness - I can start that naive algorithm from left end or right end or from the middle - how different results I would get ? And probably there are other algorithms which will they give completely other outcome - is it so ? Or the reasobale outcome is unque plus-minus ? About "to be more precise" yes I am worried, but detailed explanation would overload the question, so I am leaving it open-ended: it should be reasonable - not "average everything" – Alexander Chervov Mar 2 at 12:14