0
$\begingroup$

$\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?

$\endgroup$
1
$\begingroup$

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} $$

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

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)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.