Let $S\_n$ be defined as $\frac{1}{n}\sum\_{t=1}^{t=n} [x^2+(p-q)x]$ where $x = 1-(1-p-q)^t$. We want to find the conditions on $p$ and $q$ such that $S\_n$ is monotonically decreasing for all $n$. $0 < p,q < 1$ and $0 < 1-p-q < 1$.


Note:
Till now I have tried to get a closed bound expression for $S\_n$ and differentiate it w.r.t. $n$ to get the conditions for a negative slope but it is getting really complex.


Another approach was to reduce this expression to the sum $S\_n = C (>0) + \frac{1}{n}\left[q\sum\_{t=1}^{n} \lambda^{2t} + (p-q) \sum\_{t=1}^{n} \lambda^t \right]$ where $\lambda=1-p-q$. We know the upper bounds of the two sums, and since the denominator grows more rapidly than the numerator, it is sufficient to show that the numerator is positive to get a monotonically decreasing sequence.



Prove that the following running average is monotonically decreasing
$S\_n$ is always *increasing* in $n$. Note that $x$ is increasing in $t$; therefore, if $p\geq q$, then $x^2+(p-q)x$ is increasing in $t$.


If $q > p$, then you can set $a=1-p-q$, and $b=1-p+q$. The condition is $0<a\leq b<1$, and $x^2+(p-q)x=x(x-1+b)=(1-a^t)(b-a^t)$, which is increasing in $t$.


