# Converting a double summation involving absolute distances to a single summation

$\sum\limits_{i=0}^n \sum\limits_{j=0}^n p_i p_jt_{ij}$, where $0 \leq p_i,p_j \leq 1$ and $t_{ij}$ is a distance function $t_{ij} = |i-j| \forall i,j \in \mathbb{N}$

How can I convert the above double sum to a single sum?

I reached the following:

Since $t_{ij} = |i-j|$, if we denote $a_{ij} = p_ip_j|i-j|$ and put $a_{ij}$ in a matrix where $i$ is the row number and $j$ is the column number it will be a symmetric one with the diagonal zero, so it is enough to calculate the sum of the upper-right triangle of the matrix and multiply by two. The sum of the upper right triangle is: $$1p_1p_2 + 2p_1p_3 +...+ (n-1)p_1p_n+1p_2p_3+2p_2p_4+...+(n-2)p_2p_n+....+1p_{n-1}p_n.$$ But this is clearly equal to $p_1(p_2+p_3+...+p_n) + (p_1+p_2)(p_3 + p_4 +...+p_n) \ldots$

How can I write the last thing I reached as a single sum?

Not sure if this is what you need, but if $k \in [0,n^2]$ then $i = \lfloor k/n \rfloor$ and $j = k \pmod{n}$ do what you need, so you can write $$\sum_{i=0}^n \sum_{j=0}^n f(i,j) = \sum_{k=0}^{n^2} f\left(\lfloor k/n \rfloor, k \pmod{n}\right)$$

UPDATE

May be you were looking to write that last sum as a compact expression? $$\sum_{k=1}^{n-1} \sum_{i=1}^k p_i \sum_{i=k+1}^n p_i$$ If you assume your probabilities satisfy $p_1 + \ldots + p_n = 1$, you also get $$\begin{split} \sum_{k=1}^{n-1} \sum_{i=1}^k p_i \sum_{i=k+1}^n p_i &= \sum_{k=1}^{n-1} \sum_{i=1}^k p_i \left(1 - \sum_{i=1}^k p_i\right)\\ &= \sum_{k=1}^{n-1} \sum_{i=1}^k p_i - \sum_{k=1}^{n-1} \left(\sum_{i=1}^k p_i\right)^2 \\ &= \sum_{k=1}^{n-1} (n-k)p_k - \sum_{k=1}^{n-1} \left(\sum_{i=1}^k p_i\right)^2 \end{split}$$

• This does not look like what I need. I do not understand that is the purpose of $k$ here.. – TheNotMe Jul 17 '17 at 18:59
• @TheNotMe you wanted a single sum, so i converted a double sum for you into a single sum – gt6989b Jul 17 '17 at 21:09

I'm not sure about what you are asking for but here is a way to write it in a single sum.

Let $M$ the matrix such that $M_{ij} = t_{ij} = |i-j|$ and $P$ the vector of all $p_i$. $M$ is symmetric so it exists $Q$ orthogonal and $D = (d_{ii})$ diagonal such that $M=Q^T D Q$. Then you have: $$\sum_{i=1}^n \sum_{j=1}^n p_ip_j t_{ij} = P^T M P = P^TQ^T D QP = (QP)^TD(QP) = \sum_{i=1}^n d_{ii} (QP)_i^2$$

However, I do not know if $Q$ has a nice expression that would be simple enough for you.

Note that the sum you provided is actually not a single sum since it can be written: $$\sum_{i=1}^{n-1}\left( \left( \sum_{j=1}^i p_j \right)\left( \sum_{j=i+1}^n p_j \right) \right)$$