3.1. A first bound on the convergence time

We introduce $\lambda$ , the distance between $\ell$ and its nearest integer, that is,

\[\lambda \,:\!=\, \min \{\ell-\lfloor \ell \rfloor, \lceil \ell \rceil -\ell \} = \min \{\ell-\lfloor \ell \rfloor, 1 - (\ell-\lfloor \ell \rfloor)\}.\]

It is easily checked that we have $0 \leq \lambda \leq 1/2$ . In Theorem 4 of [Reference Mocquard, Anceaume and Sericola11] we dealt with the case where $\lambda$ is equal to $1/2$ . In the following we extend that analysis first to the case where $\lambda = (n- 1_{\{n\,\mathrm{odd}\} })/(2n)$ (see Theorem 2) and then to all $\lambda \in [0,1/2]$ (see Section 3.2). We start with the following two lemmas.

Lemma 2. Let $h = \lfloor \ell \rfloor + 1/2$ and $H = (h,h,\ldots,h) \in \mathbb{R}^n$ . If $\lambda = (n- 1_{\{n\,\mathrm{odd}\} })/(2n)$ , then

(5) \begin{equation}\|C_t-L\|^2 = \|C_t-H\|^2 - \dfrac{1_{\{n \,\mathrm{odd}\}}}{4n} \geq \dfrac{n}{4} - \dfrac{1_{\{n \,\mathrm{odd}\}}}{4n}.\end{equation}

Proof. Vector $C_t-L$ is orthogonal to vector e, with all entries equal to 1. Indeed,

\begin{equation*}\langle C_t-L, e \rangle = \sum_{i = 1}^{n} \bigl(C_t^{(i)} - \ell\bigr) = n \ell - n \ell = 0.\end{equation*}

Hence, since $L - H = (\ell - h) e$ , we deduce that $C_t-L$ and $L-H$ are orthogonal too. Applying Pythagoras’ theorem, we obtain

(6) \begin{equation}\|C_t-L\|^2 = \|C_t-H\|^2 - \|L-H\|^2.\end{equation}

Moreover, we have $\|L-H\|^2 = n(\ell -h)^2 =n (1/2 - (\ell -\lfloor \ell \rfloor))^2$ . By definition of $\lambda$ and since $\lambda = (n-1_{\{n\,\mathrm{odd}\}})/(2n)$ , we have either $\ell -\lfloor \ell \rfloor=(n-1_{\{n\,\mathrm{odd}\}})/2n$ or $\ell -\lfloor \ell \rfloor=(n+1_{\{n\,\mathrm{odd}\}})/2n$ . In both cases we get

(7) \begin{equation}\|L-H\|^2 = \dfrac{1_{\{n\,\mathrm{odd}\}}}{4n}.\end{equation}

Observe that

(8) \begin{equation}\|C_t-H\|^2 \geq n \min_{1 \leq i \leq n } |C^{(i)}_t- (\lfloor \ell \rfloor + 1/2)|^2 \geq n |1/2|^2 = n/4.\end{equation}

Substituting (7) in relation (6), and applying inequality (8), we get inequality (5).

Lemma 3. If $\lambda = (n- 1_{\{n\,\mathrm{odd}\} })/(2n)$ , then we have

\begin{equation*} \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 \Longleftrightarrow \|C_t-L\|_{\infty} > 1-\lambda =\dfrac{n+1_{\{n \,\mathrm{odd}\}}}{2n}.\end{equation*}

Proof. Since $\lambda > 0$ , $\ell$ is not an integer, so

\[\max_{1\leq i\leq n} C_{t}^{(i)} \geq \lceil \ell \rceil \quad \text{and} \quad \min_{1\leq i\leq n} C_{t}^{(i)} \leq \lfloor \ell \rfloor,\]

which implies that $\|C_t-L\|_{\infty} \geq 1-\lambda$ . Thus

\[\max_{1\leq i\leq n} C_{t}^{(i)}- \min_{1\leq i\leq n} C_{t}^{(i)} = 1\]

implies that

\[\max_{1\leq i\leq n} C_{t}^{(i)} = \lceil \ell \rceil \quad \text{and} \quad \min_{1\leq i\leq n} C_{t}^{(i)} = \lfloor \ell \rfloor,\]

which means that $\|C_t-L\|_{\infty} = 1-\lambda$ .

Conversely, if $\|C_t-L\|_{\infty} = 1-\lambda$ , then we have $\ell-1 < C_t^{(i)}< \ell+1$ , which means that

\[\max_{1\leq i\leq n} C_{t}^{(i)} = \lceil \ell \rceil \quad \text{and} \quad \min_{1\leq i\leq n} C_{t}^{(i)} = \lfloor \ell \rfloor, \]

that is,

\begin{equation*} \max_{1\leq i\leq n} C_{t}^{(i)}- \min_{1\leq i\leq n} C_{t}^{(i)} = 1. \end{equation*}

This completes the proof.

We can now prove the following theorem.

Theorem 2. For all $\delta \in (0,1)$ , if $\lambda = (n- 1_{\{n\,\mathrm{odd}\} })/(2n)$ and if there exists a constant K such that $\|C_{0}-L\| \leq K$ , then, for every $t \geq (n-1) (2\ln{K}-\ln{\delta}-\ln{2})$ , we have

\begin{equation*} \mathbb{P}\biggl\{ \|C_t-L\|_\infty > \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n}\biggr\} = \mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 \Bigr\} \leq \delta,\end{equation*}

or equivalently

(9) \begin{equation}\mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}= \min_{1\leq i\leq n} C_{t}^{(i)} + 1 \Bigr\} \geq 1 - \delta.\end{equation}

Proof. We first show that

(10) \begin{equation}\max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 \Longrightarrow \|C_t-L\|^2 \geq \dfrac{n}{4} -\dfrac{1_{\{n\,\mathrm{odd}\}}}{4n} +2.\end{equation}

Let $h = \lfloor \ell \rfloor + 1/2$ and $H = (h,h,\ldots,h) \in \mathbb{R}^n$ . In the same way, if $\max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1$ , then there exists an agent i such that $|C_t^{(i)}-h| \geq 3/2$ , and for all $j \in \{1,2,\ldots,n\} \setminus \{i\}$ , $|C_t^{(j)}-h| \geq 1/2$ . We can thus write

\begin{align*}\max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 & \implies \|C_t-H\|^2 \geq \dfrac{n-1}{4}+\biggl(\dfrac{3}{2}\biggr)^2 = \dfrac{n}{4}+2.\end{align*}

Applying Lemma 2, we thus obtain relation (10), and deduce that

(11) \begin{equation}\mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 \Bigr\} \leq \mathbb{P}\biggl\{ \|C_t-L\|^2 \geq \dfrac{n}{4} -\dfrac{1_{\{n\,\mathrm{odd}\}}}{4n} +2 \biggr\}.\end{equation}

Then, from relation (3) of Theorem 1, we obtain

\[\mathbb{E}\biggl(\|C_t-L\|^2-\dfrac{n}{4}+\dfrac{1_{\{n\,\mathrm{odd}\}}}{4n}\biggr) \leq \biggl(1-\dfrac{1}{n-1}\biggr)^t\mathbb{E}(\|C_0-L\|^2).\]

Let $\tau = (n-1) (2\ln{K}-\ln{\delta}-\ln{2})$ . For $t \geq \tau$ , we have

\[ \biggl(1-\dfrac{1}{n-1}\biggr)^t \leq {\mathrm{e}}^{-t/(n-1)} \leq {\mathrm{e}}^{-\tau/(n-1)} = \dfrac{2\delta}{K^2}.\]

Moreover, since $\|C_0-L\| \leq K$ , we get $\mathbb{E}(\|C_0-L\|^2) \leq K^2$ and thus

\[\mathbb{E}\biggl(\|C_t-L\|^2-\dfrac{n}{4}+\dfrac{1_{\{n\,\mathrm{odd}\}}}{4n}\biggr) \leq 2\delta.\]

Using the Markov inequality (Lemma 2 ensures that we take the expectation of a non-negative random variable), we obtain for $t \geq \tau$

\[\mathbb{P}\biggl\{\|C_t-L\|^2 - \dfrac{n}{4} + \dfrac{1_{\{n\,\mathrm{odd}\}}}{4n} \geq 2\biggr\} \leq \delta.\]

Hence we deduce from relation (11) that, for $t \geq \tau$ ,

\[\mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 \Bigr\} \leq \delta.\]

Note that $\max_{1\leq i\leq n} C_{t}^{(i)}$ cannot be equal to $\min_{1\leq i\leq n} C_{t}^{(i)}$ here. Indeed, if so, then vector $C_t$ is equal to vector L, implying that $\ell$ is an integer. In such a case we have $\lambda = 0$ , which is impossible since $n \geq 2$ . Hence

\[\mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} \leq 1 \Bigr\} = \mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}= \min_{1\leq i\leq n} C_{t}^{(i)} + 1 \Bigr\}\]

and we directly obtain relation (9). Finally, applying Lemma 3, we deduce that

\[\mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 1 \Bigr\} = \mathbb{P}\biggl\{ \|C_t-L\|_\infty > \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n} \biggr\},\]

which ends the proof.

Note that

\[\max_{1\leq i\leq n} C_{t}^{(i)}= \min_{1\leq i\leq n} C_{t}^{(i)} + 1\]

implies that

\[\min_{1\leq i\leq n} C_{t}^{(i)} = \lfloor \ell \rfloor \quad \text{and} \quad \max_{1\leq i\leq n} C_{t}^{(i)} = \lceil \ell \rceil.\]

Hence Theorem 2 assures us that if $\lambda= (n- 1_{\{n\,\mathrm{odd}\} })/(2n)$ , then the protocol converges after at least $ (n-1) (2\ln{K}-\ln{\delta}-\ln{2})$ interactions, with arbitrarily high probability $1-\delta$ , towards a class of absorbing states which are vectors with entries equal to either $ \lfloor \ell \rfloor $ or $ \lceil \ell \rceil $ .

3.2. The shadow process and the main result

The goal of this section is to obtain a result identical to that of Theorem 2, but without any assumption on $\lambda$ . This is done by using a stochastic coupling technique in which the process coupled with process C is called the shadow process of C.

The shadow process associated with process C is denoted by $D\,:\!=\,\{D_t, \; t \geq 0\}$ and defined at time $t=0$ by $D_0^{(i)} = C_0^{(i)} +1_{\{i \in B_0\}}$ , where $B_0$ is any fixed non-empty subset of b agents with $b \leq n-1$ , i.e. $B_0 \subset \{1,\ldots,n\}$ and $|B_0|=b$ .

For every $t \geq 1$ , the random vector $D_t$ is defined as $C_t$ , that is, when the couple (i, j) is chosen to interact at time t, i.e. when $X_t=(i,j)$ , the vector $D_{t+1}$ is given by

\begin{align*}\Bigl(D_{t+1}^{(i)},D_{t+1}^{(j)}\Bigr) = \Biggl(\Biggl\lfloor \dfrac{D_{t}^{(i)} + D_{t}^{(j)}}{2} \Biggr\rfloor,\Biggr\lceil \dfrac{D_{t}^{(i)} + D_{t}^{(j)}}{2}\Biggr\rceil \Biggr) \quad \text{and} \quad D_{t+1}^{(r)} = D_{t}^{(r)} \quad \text{for } r \neq i,j.\end{align*}

In other words, processes $C_t$ and $D_t$ are coupled by process $X_t$ : they behave identically in the sense that at each time, the same two agents are chosen for the interaction. The only difference lies in their initial values. Lemma 4 shows that if at time $t=0$ , $D_0$ is initially in the shadow of $C_0$ , then at any time $t\geq 0$ , $D_{t}$ remains in the shadow of $C_{t}$ .

Lemma 4. For all $t\geq 0$ , there exists a non-empty set $B_t$ of b agents, i.e. $B_t \subset \{ 1,\ldots,n\}$ and $|B_t|=b$ , such that, for all $i \in \{ 1, 2, \ldots, n\}$ , we have

(12) \begin{equation}D_t^{(i)} = C_t^{(i)} +1_{\{i \in B_t\}}.\end{equation}

Proof. The proof is made by induction. Relation (12) is clearly true for $t=0$ by definition of $D_0$ . Suppose that at time $t \geq 0$ there exists a set $B_{t} \subset \{1,2,\ldots,n\}$ with $|B_{t}|=b$ , satisfying relation (12). Let i and j be the two agents interacting at time t, that is, let $X_t = (i, j)$ , for both processes $C_t$ and $D_t$ . We distinguish the following cases.

• Case 1: $i,j \in B_t$ . In this case we have

  \[D_{t+1}^{(i)} =\biggl\lfloor\dfrac{D_{t}^{(i)} + D_{t}^{(j)}}{2}\biggr\rfloor= \biggl\lfloor\dfrac{C_{t}^{(i)} + C_{t}^{(j)}+2}{2}\biggr\rfloor=C_{t+1}^{(i)}+1.\]
  In the same way we have $D_{t+1}^{(j)} = C_{t+1}^{(j)}+1$ , which means that $i,j \in B_{t+1}$ . The other entries being invariant, we have $B_{t+1} = B_t$ .

• Case 2: $i,j \notin B_t$ . In this case we have $D_{t+1}^{(i)}=C_{t+1}^{(i)}$ and $D_{t+1}^{(j)}=C_{t+1}^{(j)}$ which means that $i,j \notin B_{t+1}$ . The other entries being invariant, we have $B_{t+1} = B_t$ .

• Case 3.1: $i \in B_t$ and $j \notin B_t$ and $C_t^{(i)} + C_t^{(j)}$ is even. In this case we have

  \[D_{t+1}^{(i)} =\biggl\lfloor\dfrac{D_{t}^{(i)} + D_{t}^{(j)}}{2}\biggr\rfloor= \biggl\lfloor\dfrac{C_{t}^{(i)} + 1 + C_{t}^{(j)}}{2}\biggr\rfloor= \biggl\lfloor\dfrac{C_{t}^{(i)} + C_{t}^{(j)}}{2}\biggr\rfloor = C_{t+1}^{(i)}.\]
  In the same way we have $D_{t+1}^{(j)}=C_{t+1}^{(j)}+1$ , which means that $i \notin B_{t+1}$ and $j \in B_{t+1}$ . We thus have $B_{t+1} = (B_t \setminus \{i\}) \cup \{j\}$ and so $|B_{t+1}| = |B_t|=b$ .

• Case 3.2: $i \in B_t$ and $j \notin B_t$ and $C_t^{(i)} + C_t^{(j)}$ is odd. In a similar way to Case 3.1, we have $D_{t+1}^{(i)}=C_{t+1}^{(i)}+1$ and $D_{t+1}^{(j)}=C_{t+1}^{(j)}$ , which means that $i \in B_{t+1}$ and $j \notin B_{t+1}$ and so $B_{t+1} = B_t$ .

• Case 4.1: $i \notin B_t$ and $j \in B_t$ and $C_t^{(i)} + C_t^{(j)}$ is even. In a similar way to Case 3.2, we have $D_{t+1}^{(i)}=C_{t+1}^{(i)}$ and $D_{t+1}^{(j)}=C_{t+1}^{(j)}+1$ , which means that $i \notin B_{t+1}$ and $j \in B_{t+1}$ and so $B_{t+1} = B_t$ .

• Case 4.2: $i \notin B_t$ and $j \in B_t$ and $C_t^{(i)} + C_t^{(j)}$ is odd. In a similar way to Case 3.1, we have $D_{t+1}^{(i)}=C_{t+1}^{(i)}+1$ and $D_{t+1}^{(j)}=C_{t+1}^{(j)}$ , which means that $i \in B_{t+1}$ and $j \notin B_{t+1}$ . We thus have $B_{t+1} = (B_t \setminus \{j\}) \cup \{i\}$ and so $|B_{t+1}| = |B_t|=b$ .

In all cases we have shown that $B_{t+1} \subset \{1,2,\ldots,n\}$ , that $|B_{t+1}|=|B_{t}|=b$ , and that (12) is true at time $t+1$ , which completes the proof.

Just as for process C, we let $\ell_D$ denote the mean value of the entries of $D_t$ and let $L_D$ denote the row vector of $\mathbb{R}^n$ with all its entries equal to $\ell_D$ , that is,

\[\ell_D \,:\!=\, \dfrac{1}{n}\sum_{i=1}^n D_{t}^{(i)} \quad \text{and} \quad L_D \,:\!=\, (\ell_D,\ldots,\ell_D).\]

We use the shadow process D to extend the results of Theorem 2 for any value of $\lambda$ . We first show that for any process C we can construct a shadow process D verifying the condition of Theorem 2, that is, a shadow process D such that the fractional part $\lambda_D$ of $\ell_D$ , defined by

\[\lambda_D \,:\!=\, \min \{\ell_D-\lfloor \ell_D \rfloor, \lceil \ell_D \rceil -\ell_D \} = \min \{\ell_D-\lfloor \ell_D \rfloor, 1 - (\ell_D-\lfloor \ell_D \rfloor)\},\]

verifies

\[\lambda_D= \dfrac{n-1_{\{n \,\mathrm{odd}\}} }{2n}.\]

Recall from relation (2) and Lemma 1 that $n\ell = \sum_{i = 1}^nC^{(i)}_0 $ is an integer.

Proof. Let $B_0$ be a set of b agents with $b \in \{1,\ldots, n-1\}$ and let $D_t$ be the corresponding shadow process, associated with process $C_t$ , defined in Section 3.2. By definition of $\ell_D$ , we have, from (12), $\ell_D = \ell + b/n$ , which gives $\ell_D - \lfloor \ell_D\rfloor = \ell + b/n -\lfloor \ell + b/n \rfloor$ . Let d be the smallest integer such that n divides $n \ell + d$ . Integer d thus belongs to $\{0,\ldots,n-1\}$ , and we have $\ell_D - \lfloor \ell_D\rfloor = (b - d)/n -\lfloor (b - d)/n \rfloor$ .

• Case 1: if $0 \leq d \leq n/2$ then, by taking $b = d + (n - 1_{\{n \,\mathrm{odd}\}})/2$ , we check that $b \in \{1,\ldots, n-1\}$ . Since $0 < (n-1_{\{n \,\mathrm{odd}\}})/(2n) < 1$ , we have

  \begin{equation*}\ell_D - \lfloor \ell_D\rfloor = \dfrac{n - 1_{\{n \,\mathrm{odd}\}}}{2n} -\biggl\lfloor \dfrac{n - 1_{\{n \,\mathrm{odd}\}}}{2n} \biggr\rfloor = \dfrac{n - 1_{\{n \,\mathrm{odd}\}}}{2n}.\end{equation*}

• Case 2: if $n/2 < d < n$ then, by taking $b = d - (n + 1_{\{n \,\mathrm{odd}\}})/2$ , we also check that $b \in \{1,\ldots, n-1\}$ . Since $-1 < -(n + 1_{\{n \,\mathrm{odd}\}})/(2n) < 0$ , we have

  \begin{equation*}\ell_D - \lfloor \ell_D\rfloor = -\dfrac{n + 1_{\{n \,\mathrm{odd}\}}}{2n} -\biggl\lfloor -\dfrac{n + 1_{\{n \,\mathrm{odd}\}}}{2n} \biggr\rfloor = \dfrac{n - 1_{\{n \,\mathrm{odd}\}}}{2n}.\end{equation*}

Hence $\ell_D - \lfloor \ell_D\rfloor = (n-1_{\{n \,\mathrm{odd}\}} )/(2n)$ , which ends the proof.

The shadow process D, associated with process C, is thus constructed from the remainder of the Euclidean division of $n \ell$ by n. Taking the complement of this remainder to n, we deduce the value of parameter b of the shadow process D. In order to prove the main theorem of this paper, we still need the following technical result.

Lemma 6. For all $t\geq 0$ , we have

\[\|C_t-L\|_{\infty} - \|D_t-L_D\|_{\infty} \leq \dfrac{n-1}{n} \quad \text{and} \quad \|D_t-L_D\| - \|C_t-L\| < \sqrt{n}.\]

Proof. From Lemma 4 we easily get

\[\ell_D = \dfrac{1}{n}\sum_{i=1}^n D_{t}^{(i)}= \ell + \dfrac{|B_t|}{n}=\ell + \dfrac{b}{n}.\]

Observing that

\begin{align*}\|D_t-L_D\|_\infty & = \max\Bigl\{\ell_D-\min_{1\leq i \leq n}D_t^{(i)},\max_{1\leq i \leq n}D_t^{(i)}-\ell_D\Bigr\}, \\\|C_t-L\|_\infty & = \max\Bigl\{\ell-\min_{1\leq i \leq n}C_t^{(i)},\max_{1\leq i \leq n}C_t^{(i)}-\ell\Bigr\},\end{align*}

we first deduce that

(13) \begin{equation} \|D_t-L_D\|_\infty \geq \Bigl(\ell_D-\min_{1\leq i \leq n}D_t^{(i)} \Bigr) \quad \text{and} \quad \|D_t-L_D\|_\infty \geq \Bigl(\max_{1\leq i \leq n}D_t^{(i)}-\ell_D\Bigr).\end{equation}

We distinguish the following two cases. If $\|C_t-L\|_\infty = \ell - \min_{1 \leq i \leq n }{C_t^{(i)}}$ , then, applying relation (13), we obtain

\begin{equation*}\|C_t-L\|_\infty -\|D_t-L_D\|_\infty \leq \Bigl(\ell - \min_{1 \leq i \leq n }{C_t^{(i)}} \Bigr) - \Bigl(\ell_D-\min_{1 \leq i \leq n }{D_t^{(i)}} \Bigr),\end{equation*}

and since, from Lemma 4, we have $\min_{1 \leq i \leq n }{D_t^{(i)}} \leq \min_{1 \leq i \leq n }{C_t^{(i)}} + 1$ , we deduce

\begin{equation*}\|C_t-L\|_\infty -\|D_t-L_D\|_\infty \leq \ell - \ell_D + 1 = 1 - \dfrac{b}{n} \leq \dfrac{n-1}{n}.\end{equation*}

If $\|C_t-L\|_\infty = \max_{1\leq i \leq n}C_t^{(i)}-\ell$ , then, applying relation (13), we obtain

\begin{equation*}\|C_t-L\|_\infty -\|D_t-L_D\|_\infty \leq \Bigl(\max_{1\leq i \leq n}C_t^{(i)}-\ell \Bigr)- \Bigl(\max_{1\leq i \leq n}D_t^{(i)}-\ell_D\Bigr),\end{equation*}

and since, from Lemma 4, we have $\max_{1 \leq i \leq n }{C_t^{(i)}} \leq \max_{1 \leq i \leq n }{D_t^{(i)}}$ , we again deduce

\begin{equation*}\|C_t-L\|_\infty -\|D_t-L_D\|_\infty \leq \ell - \ell_D = \dfrac{b}{n} \leq \dfrac{n-1}{n},\end{equation*}

which completes the proof of the first inequality.

To prove the second one, note that $D_t-L_D$ is orthogonal to unit vector e. Indeed

\begin{equation*}\langle D_t-L_D, e \rangle = \sum_{i = 1}^{n} (D_t^{(i)} - \ell_D) = n \ell_D - n \ell_D = 0.\end{equation*}

Hence, since $L_D-L = (\ell_D - \ell) e$ , we deduce that $D_t-L_D$ and $L_D-L$ are orthogonal too. Pythagoras’ theorem then gives $\|D_t-L\|^2=\|D_t-L_D\|^2 +\|L_D-L\|^2$ , which implies that $\|D_t-L_D\| \leq \|D_t-L\|$ .

From relation (12), we have $D_t^{(i)}-C_t^{(i)} = 1_{\{i \in B_t\}}$ for every $i=1,\ldots,n$ . Since $|B_t|=b$ , this leads to $\|D_t-C_t\|=\sqrt{b}$ . From the triangle inequality and since $b < n$ , we get $\|D_t-L\| \leq \|D_t-C_t\| + \|C_t-L\| = \|C_t-L\|+\sqrt{b} \leq \|C_t-L\|+\sqrt{n}$ .

The following theorem is the main result of this paper.

Theorem 3. For all $\delta \in (0,1)$ , if there exists a constant K such that $\|C_{0}-L\| \leq K$ , then, for all $t \geq (n-1) (2\ln{(K+\sqrt{n})}-\ln{\delta}-\ln{2})$ , we have

(14) \begin{equation}\mathbb{P} \{\|C_t-L\|_\infty \geq 3/2\} \leq \delta.\end{equation}

Proof. Let d be the smallest integer such that n divides $n \ell + d$ . From Lemma 5 there exists a shadow process D associated with a set $B_0$ of b agents, such that

\[\ell_D - \lfloor \ell_D\rfloor = \dfrac{b - d}{n} -\biggl\lfloor \ell + \dfrac{b - d}{n} \biggr\rfloor = \dfrac{n-1_{\{n \,\mathrm{odd}\}}}{2n}.\]

Hence

\[\lambda_D = \min \biggl(\dfrac{n-1_{\{n \,\mathrm{odd}\}}}{2n}, 1-\dfrac{n-1_{\{n \,\mathrm{odd}\}}}{2n} \biggr) = \dfrac{n-1_{\{n \,\mathrm{odd}\}}}{2n}.\]

Moreover, combining the hypothesis $\|C_{0}-L\| \leq K$ and Lemma 6, we get $\|D_{0}-L_D\| \leq \|C_{0}-L\| + \sqrt{n} \leq K + \sqrt{n}$ . We can thus apply Theorem 2 to process D with $\lambda_D$ , $L_D$ , and $K+\sqrt{n}$ in place of $\lambda$ , L, and K respectively. We thus obtain, for all $\delta \in (0,1)$ and for every $t\geq (n-1) (2\ln(K+\sqrt{n}) -\ln\delta -\ln 2)$ ,

\[\mathbb{P}\biggl\{ \|D_t-L_D\|_\infty > \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n}\biggr\} = \mathbb{P}\Bigl\{ \max_{1\leq i\leq n} D_{t}^{(i)}-\min_{1\leq i\leq n} D_{t}^{(i)} > 1 \Bigr\} \leq \delta.\]

From Lemma 6, we get $\|C_t-L\|_\infty \leq \|D_t-L_D\|_\infty +{{(n-1)}/{n}}.$ This inequality allows us to write

\[\|D_t-L_D\|_\infty \leq \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n} \implies \|C_t-L\|_\infty \leq \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n} + \dfrac{n-1}{n} < \dfrac{3}{2},\]

and thus

\[\mathbb{P}\biggl\{\|C_t-L\|_\infty < \dfrac{3}{2}\biggr\}\geq \mathbb{P}\biggl\{ \|D_t-L_D\|_\infty \leq \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n}\biggr\},\]

or equivalently

\[\mathbb{P}\biggl\{\|C_t-L\|_\infty\geq \dfrac{3}{2}\biggr\}\leq \mathbb{P}\biggl\{ \|D_t-L_D\|_\infty > \dfrac{n+1_{\{n\,\mathrm{odd}\}}}{2n}\biggr\} \leq \delta,\]

which completes the proof.

Theorem 3 thus extends the results of Theorem 6 of [Reference Mocquard, Anceaume and Sericola11] to any $\lambda $ . For any $\lambda $ , process $C_t$ belongs to the open ball of radius $3/2$ and center L, with arbitrarily high probability in the infinity norm, after no more than ${\mathrm{O}}(n \ln( K + \sqrt{n}))$ time or ${\mathrm{O}}(\ln(K + \sqrt{n}))$ parallel time, as shown in relation (14). Note that in relation (14) we explicitly give the constant arising in this complexity. This constant depends on the upper bound K of $\|C_{0}-L\|$ and the initial vector $C_0$ is given by the application the user wants to deal with. In the next section we calculate the upper bound K for two different types of application: the proportion problem and the system size problem. We conclude this section with the following corollary, which shows that under the condition of Theorem 3, the greatest difference among the entries of vector $C_t$ , which represents the values of the agents at time t, is less than or equal to 2 with arbitrarily high probability.

Corollary 1. For all $\delta \in (0,1)$ , if there exists a constant K such that $\|C_{0}-L\| \leq K$ , then for all $t \geq (n-1) (2\ln{(K+\sqrt{n})}-\ln{\delta}-\ln{2})$ , we have

\begin{equation*} \mathbb{P}\Bigl\{ \max_{1\leq i\leq n} C_{t}^{(i)}-\min_{1\leq i\leq n} C_{t}^{(i)} > 2 \Bigr\} \leq \delta .\end{equation*}

Proof. Observe that

\begin{align*}\|C_t - L \|_{\infty} < 3/2& \Longleftrightarrow \max_{ 1 \leq i \leq n } C^{(i)}_t - \ell < 3/2 \quad \text{and} \quad \ell - \min_{ 1 \leq i \leq n } C^{(i)}_t < 3/2 \\& \Longrightarrow \max_{ 1 \leq i \leq n } C^{(i)}_t - \min_{ 1 \leq i \leq n } C^{(i)}_t < 3.\end{align*}

This leads to

\[\mathbb{P}\{\|C_t - L \|_{\infty} < 3/2\} \leq \mathbb{P}\Bigl\{\max_{1 \leq i \leq n} C^{(i)}_t - \min_{1 \leq i \leq n} C^{(i)}_t \leq 2\Bigr\},\]

since the $C^{(i)}_t$ are integers, and we conclude by applying Theorem 3.

4.1. Solving the proportion problem

The proportion problem requires each agent to compute the proportion $\gamma_A$ of agents that initially started the average-based algorithm with initial value A. We have $\gamma_A=n_A/n$ . Recall that the number n of agents in the system is not known to the agents. Relation (15) gives a function of $n_A$ , which reaches its maximum for $n_A = n/2$ . At that value we obtain $\|C_0-L\|^2 \leq m^2 n /4$ , that is,

(16) \begin{equation} \|C_0-L\| \leq m \sqrt{n}/2.\end{equation}

Recall that $C_t^{(i)}$ represents the local value of agent i at discrete time t. We show that the local estimation of the proportion $\gamma_A$ is given by the quantity $C_t^{(i)}/m$ . More precisely, the following theorem gives an evaluation of the first instant t from which the distance between $C_t^{(i)}/m$ and $\gamma_A$ , for all the agents, is less than a fixed $\varepsilon$ with arbitrarily high probability $1-\delta$ , the integer value m being determined by the threshold $\varepsilon$ .

Figure 1: Bound comparison of the parallel convergence time for the proportion problem. For each n, we simulate the parallel convergence time (crosses) using $10^5$ experiments. We also compute the two upper bounds on the parallel convergence time obtained in [Reference Mocquard, Anceaume and Sericola11] (dashed line) and in Theorem 4 (solid line). For each experiment the initial proportion of agents starting with A is a uniform random number in [0, 1] and we have taken $\delta = 10^{-4}$ and $\varepsilon = 10^{-2}$ , which gives $m = 150$ . Note the logarithmic scale of the x-axis.

Theorem 4. For all $\delta \in (0,1)$ and for all $\varepsilon \in (0,1)$ , by taking $m = \lceil 3/(2\varepsilon) \rceil$ , for all

\[t \geq (n-1) (\ln n -\ln \delta +2\ln(2 + 1/\varepsilon) +\ln(9/32)),\]

we have

\[\mathbb{P}\{|C_t^{(i)}/m - \gamma_A| < \varepsilon \ \text{for all } i=1,\ldots,n\} \geq 1-\delta.\]

Proof. Since $m=\lceil 3/(2\varepsilon) \rceil$ , we have, from relation (16),

\[\|C_0-L\| \leq \dfrac{m \sqrt{n}}{2} = \biggl\lceil \dfrac{3}{2\varepsilon} \biggr\rceil \dfrac{\sqrt{n}}{2}\leq \biggl(\dfrac{3}{2\varepsilon} + 1\biggr) \dfrac{\sqrt{n}}{2}= \biggl(\dfrac{3+2\varepsilon}{4\varepsilon} \biggr) \sqrt{n}.\]

By choosing $K=(3+2\varepsilon)\sqrt{n}/(2\varepsilon)$ , we obtain

\[2\ln(K+\sqrt{n}) = 2\ln\biggl[\biggl(\dfrac{3+6\varepsilon}{4\varepsilon}\biggr) \sqrt{n}\biggr]=\ln n + 2\ln(3/4) + 2\ln(2 + 1/\varepsilon).\]

We are now able to apply Theorem 3, which, for all $\delta \in (0, 1)$ and for all

\[ t \geq (n-1) (\ln n -\ln \delta +2\ln(2 + 1/\varepsilon) +\ln(9/32)), \]

leads to

\[\mathbb{P} \{\|C_t-L\|_{\infty} \geq 3/2 \} \leq \delta\]

or equivalently, since $\ell = \gamma_Am$ , to

\[\mathbb{P}\{|C_t^{(i)}/m - \gamma_A| < 3/(2m) \ \text{for all } i=1,\ldots,n\} \geq 1-\delta.\]

The fact that $m \geq 3/(2\varepsilon)$ completes the proof.

In Figure 1 we compare our new bound on the convergence time obtained in Theorem 4 for the proportion problem with that obtained in [Reference Mocquard, Anceaume and Sericola11]. One can observe that we have considerably improved it. As usual, the parallel convergence time is the convergence time divided by the number n of agents.

4.2. Solving the system size problem

We now address the system size problem and suppose that each agent knows $n_A$ . We prove that each agent is able to determine either the exact value of the number n of agents or an approximation of this number, depending on the initial input value m with arbitrarily high probability.

We introduce the following two functions, $\omega_{\min}$ and $\omega_{\max}$ , which will be used by each node to get the lower and the upper bound of n, respectively. They are defined, for all integers k, by

\[\omega_{\min}(k) = \biggl\lceil\dfrac{2n_A m}{2k + 3}\biggr\rceil \quad \text{and} \quad \omega_{\max}(k) = \begin{cases}+ \infty & \text{if } k \leq 1, \\{ \biggl\lfloor\dfrac{2n_A m}{2k - 3}\biggr\rfloor} & \text{if } k \geq 2.\end{cases}\]

We start with a general result on the convergence time for the system size problem.

Lemma 7. For all $\delta \in (0,1)$ , for all positive integers m and $n_A$ , and for all

\[ t \geq (n-1)\bigl( \ln\bigl( m\sqrt{n_A(1-n_A/n)}+ \sqrt{n}\bigr) -\ln{\delta} - \ln 2 \bigr), \]

we have

\[\mathbb{P}\bigl\{\omega_{\min}\bigl(C_t^{(i)}\bigr) \leq n \leq \omega_{\max}\bigl(C_t^{(i)}\bigr) \ \text{for all }i=1,\ldots,n\bigr\} \geq 1-\delta.\]

Proof. From (15), we obtain $\|C_0-L\|\leq m\sqrt{n_A(1-n_A/n)} $ . Applying Theorem 3 with $K= m\sqrt{n_A(1-n_A/n)}$ , we get

(17) \begin{equation} \mathbb{P} \{\|C_t-L\|_\infty < 3/2\} \geq 1-\delta,\end{equation}

for all $t \geq (n-1)\bigl(\ln(m\sqrt{n_A(1-n_A/n)}+\sqrt{n})-\ln \delta -\ln 2 \bigr)$ . Then, recalling that $\ell = n_A m/n$ and using the fact that

(18) \begin{equation} \|C_t-L\|_\infty < 3/2\Longleftrightarrow \text{for all }i=1,\ldots,n,\,\, C_t^{(i)} - 3/2 < n_A m/n < C_t^{(i)} + 3/2,\end{equation}

we deduce first that, for all $i=1,\ldots,n$ , $n_A m/(C_t^{(i)} + 3/2) < n $ , which implies that $\omega_{\min}\bigl(C_t^{(i)}\bigr) = \lceil n_A m/(C_t^{(i)} + 3/2) \rceil \leq n $ .

By definition of $\omega_{\max}$ , if $C^{(i)}_t \leq 1$ , then obviously in that case $n \leq \omega_{\max}(C_t^{(i)}) $ . If $C^{(i)}_t \geq 2$ , we deduce from relation (18) that $n < n_A m/ C_t^{(i)} - 3/2 $ , which means that $ n \leq \lfloor n_A m/(C_t^{(i)} - 3/2) \rfloor = \omega_{\max}(C_t^{(i)})$ . We have thus shown that, for all

\[t \geq (n-1)\bigl(\ln(m\sqrt{n_A(1-n_A/n)}+\sqrt{n})-\ln \delta -\ln 2 \bigr),\]

we have

(19) \begin{equation} \|C_t-L\|_\infty < 3/2 \Longrightarrow \omega_{\min}\bigl(C_t^{(i)}\bigr) \leq n \leq \omega_{\max}\bigl(C_t^{(i)}\bigr) \quad \text{for all }i=1,\ldots,n.\end{equation}

The use of relation (17) completes the proof.

Suppose that an upper bound N of n is known. Then we prove that with arbitrarily high probability, after a given number of interactions (computed below), any agent i can locally compute the exact system size n, i.e. $\omega_{\min}(C_t^{(i)})= \omega_{\max}(C_t^{(i)}) = n$ .

Theorem 5. For all $\delta \in (0,1)$ , for all positive integers $n_A$ and N with $n \leq N$ , by taking $m \geq 3N(N+1)/n_A$ , we have, for all $t \geq (n-1) (\ln{n_A}+2\ln m -\ln{\delta})$ ,

\begin{equation*} \mathbb{P}\bigl\{ \omega_{\min}\bigl(C_t^{(i)}\bigr) = \omega_{\max}\bigl(C_t^{(i)}\bigr) = n \ \text{for all }i=1,\ldots,n\bigr\} \geq 1-\delta.\end{equation*}

Proof. Since $n \leq N$ , the condition on m gives $3n(n+1) \leq n_A m$ or equivalently to $3n^2 \leq n_A m -3 n.$ Multiplying each side of this inequality by $4 n_A m /n^2$ , we obtain

(20) \begin{equation}12 n_A m \leq (2 n_A m /n )^2 - 12 n_A m /n = 4( n_A m / n - 3/2 )^2 - 9.\end{equation}

On the other hand, from (15), we have $\|C_0-L\|\leq m\sqrt{n_A(1-n_A/n)}$ . Using the fact that $\sqrt{1-x} \leq 1- x/2$ , for all $x \leq 1$ , we get

\[\|C_0-L\|\leq \sqrt{n_A}m\biggl(1-\dfrac{n_A}{2n}\biggr).\]

Letting K denote this upper bound of $\|C_0-L\|$ and using successively the condition $mn_A \geq 3n(n+1)$ and the fact that $n_A \geq 1$ , we obtain

\[K+\sqrt{n} = \sqrt{n_A}m + \sqrt{n} - \dfrac{m n_A\sqrt{n_A}}{2n} \leq \sqrt{n_A}m + \sqrt{n} - \dfrac{3(n+1)}{2}\leq \sqrt{n_A}m.\]

Using this inequality in Theorem 3, we get, for all $t \geq (n-1) (\ln n_A +2\ln m -\ln \delta -\ln 2 )$ ,

\[\mathbb{P} \{\|C_t-L\|_\infty < 3/2\} \geq 1-\delta.\]

Observe now that $\|C_t - L \|_{\infty} < 3/2$ implies that $n_Am/n - 3/2 < C_t^{(i)}$ , for all i, which in turn implies, from (20), that

\[0 \leq 12 n_A m \leq 4( n_A m / n - 3/2 )^2 - 9 < 4\big(C_t^{(i)}\big)^2 - 9,\]

in which we used the condition $m \geq 3n(n+1)/n_A$ to ensure that $n_A m / n - 3/2 > 0$ . Combining these two results and using the definitions of the integer functions $\omega_{\min}$ and $\omega_{\max}$ , we obtain

\begin{align*}\|C_t - L \|_{\infty} < 3/2& \Longrightarrow \dfrac{12 n_A m}{4( C_t^{(i)} )^2 - 9} < 1 \Longrightarrow \dfrac{2 n_A m}{2C_t^{(i)} - 3 } - \dfrac{2 n_A m}{2C_t^{(i)} + 3 } < 1 \\& \Longrightarrow \omega_{\max}\bigl(C_t^{(i)}\bigr) -\omega_{\min}\bigl(C_t^{(i)}\bigr) < 1 \Longrightarrow \omega_{\max}\bigl(C_t^{(i)}\bigr) =\omega_{\min}\bigl(C_t^{(i)}\bigr).\end{align*}

From (19) in Lemma 7, we also have

\[\|C_t - L \|_{\infty} < 3/2 \Longrightarrow \omega_{\min}\bigl(C_t^{(i)}\bigr) \leq n \leq \omega_{\max}\bigl(C_t^{(i)}\bigr) \quad \text{for all }i=1,\ldots,n.\]

Thus

\begin{equation*} 1-\delta \leq \mathbb{P} \{\|C_t-L\|_\infty < 3/2\} \leq \mathbb{P}\bigl\{\omega_{\min}\bigl(C_t^{(i)}\bigr) = \omega_{\max}\bigl(C_t^{(i)}\bigr)=n\bigr\}.\end{equation*}

This completes the proof.