# How can I show this in a summation?

I am trying to work out a summation for packet delays which is very similar to the summation for estimating RTT, which is an exponentially weighted moving average. I have modified the estimating RTT summation below (I think I did it correctly) but it does not seem to fit correctly with the part I know is right (where 0.1 has been substituted for u). If I have written this summation out correctly can someone explain why the summation raises (1-u) to the ith power and why the summation replaces u with (1-u)^n-1 and why the summation is multiplied by u/(1-u).

EDIT: If I had not looked at the estimated RTT summation this is what I would have guessed...

-
What is RTT or RRT? – Mitch Mar 31 '11 at 17:29
@Mitch RTT - Round Trip Time – ubiquibacon Mar 31 '11 at 18:14

HINT

Since there is uncertainty with 1-u, I suggest backtracking, and writing the first few terms completely out:

$d_1 = u(r_1 - t_1)$

$d_2 = (1-u)^1 u(r_1 - t_1) + u(r_2 - t_2)$

$d_3 = (1-u)^2 u(r_1 - t_1) + (1-u)^1 u(r_2 - t_2) + u(r_3-t_3)$

Now, adding in a $(1-u)^0$ which equals one, we can get:

$d_1 = (1-u)^0 u(r_1 - t_1)$

$d_2 = (1-u)^1 u(r_1 - t_1) + (1-u)^0 u(r_2 - t_2)$

$d_3 = (1-u)^2 u(r_1 - t_1) + (1-u)^1 u(r_2 - t_2) + (1-u)^0 u(r_3-t_3)$

By looking at the equations that are written out, the powers of (1-u) are of reverse magnitude to the indexes of r and t. So I think that you're looking for that in your sum. Both summations you have don't do that.

Consider this: it's possible to consolodate everything into one sum, once you match up the powers and indexes correctly.

So here's something that you can try. Take $d_2$, the equation with two terms. How do you write that as a sum, for example $d_2 = \sum_{i=0}^{2-1}{\mbox{equation}}$

Try $d_2 = u\sum_{i=0}^{2-1}{(1-u)^i(r_{2-i}-t_{2-i})}$

This should check out as being $d_2$.

Once this is confirmed, it shouldn't be too much trouble to extend this so that 2 can be replaced with n.

-
Leaving questions of clarity aside, there is no relation between what you wrote and the setting the OP describes. – Did Mar 30 '11 at 6:16
I tried to clear things up a bit, and help to answer the question. – Matt Groff Mar 30 '11 at 6:39
Sure. Your post confuses $u-1$ and $1-u$. – Did Mar 30 '11 at 7:03
Sorry. Made those corrections. I still think it may make things simple and straightforward to write out the equations. That technique has helped to eliminate confusion for me in the past. In many cases, writing out the equations helps to explain how the summation works. – Matt Groff Mar 30 '11 at 7:18
@Matt Groff yes that does make things more clear. Thanks a bunch! – ubiquibacon Mar 31 '11 at 14:55

Your $d_n$ in the first equation is the mean of the quantities $(r_i-t_i)$ where the index $i$ is chosen at random between $1$ and $n$. Calling this random index $I_n$ and introducing $\varphi(i)=r_i-t_i$, one gets $d_n=E(\varphi(I_n))$, with $P(I_n=k)=u(1-u)^{k-1}$ for every $k$ between $1$ and $n-1$ and $P(I_n=n)=(1-u)^{n-1}$. In other words, $I_n$ is distributed like $\min\{G,n\}$, where $G$ is a geometric random variable of parameter $u$. Recall that, by definition, $P(G=k)=u(1-u)^{k-1}$ for every integer $k\ge1$.

This is not consistent with what is written in the red frame. This frame reads as the recursion $d_k=u\varphi(k)+(1-u)d_{k-1}$ (with the convention that $d_0=0$), which yields $$d_n=\sum_{k=1}^nu(1-u)^{n-k}\varphi(k)+(1-u)^n\cdot 0.$$ Note the power $n-k$ (and not $k$) of $1-u$ in the coefficient of $\varphi(k)=r_k-t_k$.

-