complete w/o self-edges

Assume we have a directed weighted network on $n$ nodes that is complete (not necessarily including self-loops). That is, if $i≠j$ then $𝑻ᵢⱼ≠0$.

definition

Let $m>0$ be the minimum off-diagonal entry. Also define $U,L$ as before.

claimconvergence distance bound

$$D ≤ \frac 1 {(n-2)m} (U⁽⁰⁾-L⁽⁰⁾).$$

proof

Let $u,l$ be the indices of nodes that respectively attain maximum/minimum values at time $t+1$. Then

$$\begin{aligned} U' = xᵤ' &= ∑ⱼ₌₁ⁿ tᵤⱼ xⱼ \\ &= U + ∑ⱼ₌₁ⁿ tᵤⱼ (xⱼ-U) \\ &= U + \underbrace{tᵤᵤ}_{≥0} \underbrace{(xⱼ-U)}_{≤0} + ∑_{j≠u} \underbrace{tᵤⱼ}_{≥m} \underbrace{(xⱼ-U)}_{≤0} \\ &≤ U + m ∑_{j≠u} (xⱼ-U), \\ L' = xₗ' &≥ L + m ∑_{j≠l} (xⱼ-L), \\ U'-L' &≤ (U-L) + m \left[∑_{j≠u} (xⱼ-U) - ∑_{j≠l} (xⱼ-L)\right] \\ &≤ (U-L) + m ∑_{j≠u,l} [(xⱼ-U)-(xⱼ-L)] \\ &= [1-(n-2)m] (U-L). \end{aligned}$$

Next observe that in each step $x',x∈[L,U]$, so $x'-x≤U-L$. So then by the geometric series formula

$$D ≤ ∑ₜ₌₀^∞ [1-(n-2)m]ᵗ (U⁽⁰⁾-L⁽⁰⁾) = \frac 1 {(n-2)m} (U⁽⁰⁾-L⁽⁰⁾).$$

This bound is also tight. Consider

$$T = \begin{bmatrix} 0 & * & * & ⋯ & * \\ 1-(n-2)m & 0 & m & ⋯ & m \\ 1-(n-2)m & m & 0 & ⋯ & m \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1-(n-2)m & m & m & ⋱ & 0 \end{bmatrix}$$

(the $*$ entries can be set to non-negative values summing to $1$), with initial state $[1,0,…,0]$.

As in the previous proof (with self-edges), observe by induction that $x₂=⋯=xₙ$ and so let $A≔x₁$ and $B≔x₂=⋯=xₙ$, and we have

$$\begin{aligned} A' &= B, \\ B' &= [1-(n-2)m]A + (n-2)mB, \\ A'-B' &= -[1-(n-2)m](A-B), \\ A'-A &= B-A, \end{aligned}$$

and so

$$\begin{aligned} D &= ∑ₜ₌₀^∞ \lvert A⁽ᵗ⁺¹⁾-A⁽ᵗ⁾\rvert \\ &= ∑ₜ₌₀^∞ [1-(n-2)m]ᵗ \lvert A⁽⁰⁾-B⁽⁰⁾\rvert \\ &= \frac 1 {1-(n-2)m} \lvert A⁽⁰⁾-B⁽⁰⁾\rvert. \end{aligned}$$