next up previous
Next: Proof of Theorem 6 Up: Appendix A Previous: Proofsketch of Theorem 5

Proof of Lemma 1

The proof of this lemma is quite straightforward, but we give it for completeness. $Z$ can be rewritten as

$\displaystyle Z$ $\textstyle =$ $\displaystyle \sum_{j \neq k} {Z_{j, k}} \:\:,$ (26)

with
$\displaystyle \forall j \neq k, Z_{j, k}$ $\textstyle =$ $\displaystyle \frac{W_{j}^+}{c-1} e^{ - \frac{1}{2} \Delta(j, k) } + \frac{W_{k}^+}{c-1} e^{\frac{1}{2} \Delta(j, k)} \:\:,$ (27)

where $\Delta(j, k) = \vec{v}[j] - \vec{v}[k]$. Suppose for contradiction that for some $j<k$, $\Delta=\Delta(j, k)>0$. We simply permute the two values $\vec{v}[j]$ and $\vec{v}[k]$, and we show that the new value of $Z$ after, $Z_{\mbox{\bf a}}$, is not greater than $Z$ before permuting, $Z_{\mbox{\bf b}}$. The difference between $Z_{\mbox{\bf a}}$ and $Z_{\mbox{\bf b}}$ can be easily decomposed using the notation $Z_{(i, j)\mbox{\bf b}}$ ( $i,j \in \{0, 1, ..., c-1\}, i\neq j$) as the value of $Z_{i,j}$ (eq. (27)) in $Z_{\mbox{\bf b}}$, and $Z_{(i, j)\mbox{\bf a}}$ ( $i,j \in \{0, 1, ..., c-1\}, i\neq j$) as the value of $Z_{i,j}$ (eq. (27)) in $Z_{\mbox{\bf a}}$. We also define:
$\displaystyle \forall i,j,k \in \{0, 1, ..., c-1\}, i\neq j\neq k, Z_{(i,j,k)\m...
... Z_{(k,i),\mbox{\bf a}} + Z_{(j,k),\mbox{\bf a}} + Z_{(k,j),\mbox{\bf a}} \:\:.$     (28)

We define in the same way $Z_{(i,j,k)\mbox{\bf b}}$. We obtain
$\displaystyle Z_{\mbox{\bf a}} - Z_{\mbox{\bf b}}$ $\textstyle =$ $\displaystyle \left( Z_{(j,k)\mbox{\bf a}} -
Z_{(j,k)\mbox{\bf b}} \right) + \s...
...\}}^{c} {\left( Z_{(j,k,i)\mbox{\bf a}} - Z_{(j,k,i)\mbox{\bf b}}\right)} \:\:.$ (29)

Proving that $Z_{\mbox{\bf a}} - Z_{\mbox{\bf b}}\leq 0$ can be obtained as follows. First,

\begin{eqnarray*}
Z_{(j,k)\mbox{\bf a}} -
Z_{(j,k)\mbox{\bf b}} & = & \frac{\le...
...1}{2} \Delta}}{c-1} \left
( 1 - e^{ \Delta}\right) \leq 0 \:\:.
\end{eqnarray*}



We also have $\forall i\in\{1, 2, ..., c\} \backslash \{j, k\}$:

\begin{eqnarray*}
Z_{(j,k,i)\mbox{\bf a}} - Z_{(j,k,i)\mbox{\bf b}} & = & \frac...
...}
\Delta_{i, j}}}{c-1} \left( 1- e^{\Delta}\right) \leq 0 \:\:.
\end{eqnarray*}



Here we have use the fact that $\Delta_{i, k} = \Delta_{i, j} +
\Delta$. This shows that $Z_{\mbox{\bf a}} - Z_{\mbox{\bf b}}\leq 0$, and ends the proof of Lemma 1.


next up previous
Next: Proof of Theorem 6 Up: Appendix A Previous: Proofsketch of Theorem 5
2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.