# Multi-dimensional Lorenz-Based Chaotic Waveforms for Wireless Power Transfer

Authors  Priyadarshi Mukherjee, Member, IEEE, Constantinos Psomas, Senior
Member, IEEE, and Ioannis Krikidis, Fellow, IEEE P. Mukherjee, C. Psomas, and
I. Krikidis are with the Department of Electrical and Computer Engineering,
University of Cyprus, Nicosia 1678 (E-mail: {mukherjee.priyadarshi, psomas,
krikidis}@ucy.ac.cy). This work was co-funded by the European Regional
Development Fund and the Republic of Cyprus through the Research and
Innovation Foundation, under the projects INFRASTRUCTURES/1216/0017 (IRIDA)
and POST-DOC/0916/0256 (IMPULSE). This work has also received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant agreement No. 819819).

###### Abstract

In this paper, we investigate multi-dimensional chaotic signals with respect
to wireless power transfer (WPT). Specifically, we analyze a multi-dimensional
Lorenz-based chaotic signal under a WPT framework. By taking into account the
nonlinearities of the energy harvesting process, closed-form analytical
expressions for the average harvested energy are derived. Moreover, the
practical limitations of the high power amplifier (HPA) at the transmitter are
also taken into consideration. We interestingly observe that for these types
of signals, high peak-to-average-power-ratio (PAPR) is not the only criterion
for obtaining enhanced WPT. We demonstrate that while the HPA imperfections do
not significantly affect the signal PAPR, it notably degrades the energy
transfer performance. As the proposed framework is general, we also
demonstrate its application with respect to a Hénon signal based WPT. Finally
we compare Lorenz and Hénon signals with the conventional multisine waveforms
in terms of WPT performance.

###### Index Terms:

Wireless power transfer, multi-dimensional chaotic signal, Lorenz system,
energy harvesting.

##  I Introduction

Emerging technologies such as the Internet of Things and machine type
communications are expected to support a massive number of wireless devices.
This becomes a critical issue given their limitations in terms of energy
resources. In this context, wireless power transfer (WPT) is nowadays
attracting more and more attention [1], which refers to the transmission of
dedicated radio-frequency (RF) signals to wirelessly charge devices, located
at a certain distance from the transmitter. WPT is essentially based on the
efficient conversion of the received RF signals to direct current (DC). This
RF-to-DC conversion is typically done by a rectifying antenna (rectenna)
circuit at the receiver. The rectenna harvests electromagnetic energy from the
RF signal, followed by rectification and filtering by means of a rectifier and
a low pass filter (LPF), respectively [2]. For obtaining an enhanced WPT
performance, the choice and design of the transmitted signal is equally
important as the transmission power. Even though multitone waveforms result in
better energy transfer performance with increasing number of tones [2], the
authors in [3] claim that these signals can improve the WPT performance only
if the frequency-spacing between the neighbouring tones is properly selected.
In this context, several other signal designs have also been investigated.

The authors in [4], demonstrate that the nonlinearity at the rectenna causes
waveforms with high peak-to-average-power-ratio (PAPR) to provide a higher DC
output. The works in [5] and [6], propose the use of chaotic signals to
improve the RF-to-DC conversion efficiency, where it is experimentally
observed that chaotic signals are beneficial for WPT. The authors in [7],
propose a differential chaos shift keying (DCSK)-based WPT architecture and an
associated DCSK-based waveform, solely for WPT. Moreover, these works also
illustrate that channel fading further enhances WPT capability of chaotic
signal-based waveforms. The above studies focus on the WPT performance of
DCSK, which is an one dimensional chaotic signal. Even though experimental
results demonstrate that multi-dimensional chaotic signals are beneficial for
WPT [5, 6], no analytical framework exists, to support this claim. The
specific gains in energy harvesting (EH) from multi-dimensional chaotic
signals have not been properly explored.

Motivated by this, in this letter, we investigate multi-dimensional chaotic
signal-based waveform designs for WPT. In particular, we study a point-to-
point WPT system, where a Lorenz signal generator is used at the transmitter.
We characterize the harvested energy in terms of the parameters of the
transmitted waveform. Our study also takes into account an EH model based on
the nonlinearities of the rectification process. Even though the analytical
results provided are specifically for the Lorenz system, the framework is
general. For the sake of completeness, we have also demonstrated briefly how
the system model can be extended to a Hénon system, which is another class of
multi-dimensional chaotic systems. Extensive Monte Carlo simulations validate
the analysis. Finally, we compare the WPT performance of the Lorenz and Hénon
signal with the conventional $N$-tone multisine waveforms. To the best of our
knowledge, this is the first work that presents a complete analytical
framework for multi-dimensional chaotic signal-based WPT.

##  II System Model

Consider a point-to-point WPT set-up, where the transmitter is a Lorenz signal
generator and the receiver consists of an EH circuit that employs a rectifier
to convert the received signal to DC. A conventional Lorenz system at the
transmitter is defined as a three-dimensional nonlinear dynamical system [8]

$\displaystyle\dot{x}(t)$ $\displaystyle=\sigma(y(t)-x(t)),$ (1a)
$\displaystyle\dot{y}(t)$ $\displaystyle=x(t)(r-z(t))-y(t),$ (1b)
$\displaystyle\dot{z}(t)$ $\displaystyle=x(t)y(t)-\beta z(t),$ (1c)

where $x(t),y(t),z(t)$ are state variables, $\sigma,r,\beta>0$ are control
parameters, and $\dot{x}(t),\dot{y}(t),$ and $\dot{z}(t)$ denote
$\frac{dx(t)}{dt},\frac{dy(t)}{dt},$ and $\frac{dz(t)}{dt}$, respectively.
When a Lorenz-based transmitter is designed, the values of various circuit
components (i.e. the resistors and capacitors) at the transmitter are
controlled by $\sigma,r,$ and $\beta$, respectively.

At the receiver side, the received noisy signal is

$\tilde{x}(t)=\sqrt{P_{t}d^{-\alpha}}x(t)+n,$ (2)

where $P_{t}$ is the transmission power, $d$ is the transmitter-receiver
distance, $\alpha$ is the pathloss exponent, and $n$ is the additive white
Gaussian noise (AWGN)111In this work, we focus on the aspect of waveform
design. The consideration of fading is straightforward as we would only need
its moments [7].. It is worth noting that one of the main aspects of the
Lorenz signal, when used for the purpose of information transfer, is the
synchronization issue at the receiver [9]. However, when used for purely
energy transfer, we do not need any synchronization block at the receiver.

By considering a circuit-based nonlinear model of the harvester circuit, the
output DC current is approximated in terms of the received signal
$\tilde{x}(t)$ as [2]

$\eta_{\rm
MC}=k_{2}R_{ant}\mathbb{E}\\{|\tilde{x}(t)|^{2}\\}+k_{4}R_{ant}^{2}\mathbb{E}\\{|\tilde{x}(t)|^{4}\\},$
(3)

where the subscript MC refers to the multi-dimensional chaotic transmission.
$\eta_{\rm MC}$ is a monotonically increasing function of the DC component of
the current at the harvester output and the parameters $k_{2},k_{4},$ and
$R_{ant}$ are determined by the circuit characteristics. Any RF energy
harvesting from the AWGN is considered to be negligible and thus it is ignored
[2].

##  III Lorenz signal-based WPT

We investigate the effect of the Lorenz circuit-based chaotic signal on WPT.
The general approach to gain insights on the WPT performance of any multi-
dimensional chaotic system, is to obtain its equilibrium points and
investigate the system behavior around them [10]. As we deal with the Lorenz
system, we first obtain its corresponding equilibrium points222Although the
proposed framework is specifically for the Lorenz system, it can be extended
to any multi-dimensional chaotic circuit, namely Colpitts oscillator, Rössler
system, or Hénon system [11] (see Section III-C).. Accordingly, we evaluate
the harvested DC $\eta_{\rm MC}$ in terms of the received signal
$\tilde{x}(t)$ and its associated control parameters, i.e. $\sigma,r,$ and
$\beta$.

It should be noted that the practical implementation of (1) by means of an
electronic circuit is a complicated process due to the wide dynamic range of
the state variables $x(t),y(t),$ and $z(t)$ [9]. This bottleneck arises due to
the limited transmission capability of a practical high power amplifier (HPA)
at the transmitter, which is resolved by introducing a technique of scaling,
i.e. we scale the state variables (1) as

$x_{\rm sc}(t)=\frac{x(t)}{\epsilon_{x}},\quad y_{\rm
sc}(t)=\frac{y(t)}{\epsilon_{y}},\quad\text{and}\qquad z_{\rm
sc}(t)=\frac{z(t)}{\epsilon_{z}},$ (4)

where $\epsilon_{x},\epsilon_{y},\epsilon_{z}$ $\in[1,\infty)$ are scaling
parameters.

###  III-A Steady state analysis

By replacing (4) in (1), we obtain the scaled Lorenz system

$\displaystyle\dot{x}_{\rm sc}(t)$
$\displaystyle=\sigma\left(\frac{\epsilon_{y}}{\epsilon_{x}}y_{\rm
sc}(t)-x_{\rm sc}(t)\right),$ (5a) $\displaystyle\dot{y}_{\rm sc}(t)$
$\displaystyle=\frac{\epsilon_{x}}{\epsilon_{y}}x_{\rm
sc}(t)\left(r-\epsilon_{z}z_{\rm sc}(t)\right)-y_{\rm sc}(t),$ (5b)
$\displaystyle\dot{z}_{\rm sc}(t)$
$\displaystyle=\frac{\epsilon_{x}\epsilon_{y}}{\epsilon_{z}}x_{\rm
sc}(t)y_{\rm sc}(t)-\beta z_{\rm sc}(t).$ (5c)

To gain insights on the properties of this modified Lorenz system, we need to
locate the equilibrium points, which is computed by setting $\dot{x}_{\rm
sc}(t)=\dot{y}_{\rm sc}(t)=\dot{z}_{\rm sc}(t)=0$[10].

######  Proposition 1.

The equilibrium points $p_{\rm sc}=\left(x_{\rm eq},y_{\rm eq},z_{\rm
eq}\right)$ for a scaled Lorenz system are

$\displaystyle p_{\rm sc}=$ $\displaystyle(0,0,0),$ (6a) $\displaystyle p_{\rm
sc}=$
$\displaystyle\left(\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},\frac{\sqrt{\beta(r-1)}}{\epsilon_{y}},\frac{r-1}{\epsilon_{z}}\right),$
(6b) $\displaystyle p_{\rm sc}=$
$\displaystyle\left(-\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},-\frac{\sqrt{\beta(r-1)}}{\epsilon_{y}},\frac{r-1}{\epsilon_{z}}\right).$
(6c)

###### Proof.

See Appendix A. ∎

To further obtain insights into an $n$-dimensional nonlinear system, we fix
any $(n-1)$ parameters and observe the system behaviour with respect to the
remaining parameter [12]. Accordingly, in this case, we fix $\sigma,\beta$ and
vary $r$.

We observe from (6b) and (6c), that these equilibrium points do not exist for
$r<1$, as they must be real [10]. Furthermore, to have a stable system, $r$
can not attain any arbitrary value greater than unity. Hence, we state the
following proposition that refers to the range of $r$ that ensures system
stability.

######  Proposition 2.

Equilibrium points (6b) and (6c) are stable, if and only if,

$r\in\left(1,\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}\right).$ (7)

###### Proof.

See Appendix B. ∎

It is worth noting that $\epsilon_{x},\epsilon_{y},\epsilon_{z}$ do not have
any effect on the domain of $r$ as stated in Proposition 2. In general, Lorenz
chaotic systems are very sensitive to the initial conditions $p_{\rm
in}=(x_{0},y_{0},z_{0})$. This implies that two trajectories starting very
close together rapidly diverge after a very short span of time [12]. However,
Proposition 1 and 2 state that when
$r\in\left(1,\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}\right)$, the system
asymptotically attains (6b) or (6c) in finite time, irrespective of $p_{\rm
in}$.

As illustrated in Fig. 1, we can not accurately say to which equilibrium
point, i.e. (6b) or (6c), will $p_{\rm in}$ reach at time
$t\rightarrow\infty$; however, we can state that $p_{\rm in}$ reaches one of
them. The figure demonstrates an unscaled Lorenz system, i.e.
$\epsilon_{x}=\epsilon_{y}=\epsilon_{z}=1$, for the sake of presentation.

(a) Effect of $r$.

(b) Effect of initial point.

Figure 1: Effects of system parameters; $\sigma\\!=\\!10,\beta\\!=\\!8/3,$ and
$\epsilon_{x}\\!=\\!\epsilon_{y}\\!=\\!\epsilon_{z}\\!=\\!1$.

Fig. 1(a) depicts the effect of varying $r$ on $x(t)$, for $p_{\rm
in}=(1,-5,20)$. We observe that even for identical $p_{\rm in}$, $x(t)$
converges to different values for different $r$; the convergence rate follows
a decreasing trend with increasing $r$. Specifically, while $x(t)$
corresponding to $r=12$ converges at $t<10$, $x(t)$ corresponding to $r=18$
converges at $t\approx 20$ for the same $p_{\rm in}$. Furthermore, it is
interesting to observe from Fig. 1(b) that different $p_{\rm in}$ results in
identical steady state values at $t\rightarrow\infty$ for identical $r$. Note
that both $p_{\rm in}=(10,-5,20)$ and $p_{\rm in}=(0.1,8,0)$, with $r=12$,
attain identical $\lim\limits_{t\rightarrow\infty}x(t)$. This corroborates the
previous claim, i.e. when the system is stable, we have
$\lim\limits_{t\rightarrow\infty}x(t)\in\left\\{-\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}}\right\\}$
irrespective of $p_{\rm in}$, which is a constant quantity. However, this
uncertainty does not affect the characterization of the harvested DC, as
discussed in the next section.

###  III-B Harvested energy

From (2) and (3), we observe that $\eta_{\rm MC}$ is a function of the
$x$-component of the equilibrium points (6b) and (6c). Hence, we state the
following proposition.

######  Proposition 3.

The steady state harvested energy for a scaled Lorenz system is

$\eta_{\rm
SL}=\frac{\rho_{1}\beta(r-1)}{\epsilon_{x}^{2}}+\frac{\rho_{2}\beta^{2}(r-1)^{2}}{\epsilon_{x}^{4}},$
(8)

where $\rho_{1}=d^{-\alpha}k_{2}R_{ant}P_{t}$ and
$\rho_{2}=d^{-2\alpha}k_{4}R_{ant}^{2}P_{t}^{2}$.

###### Proof.

See Appendix C. ∎

We have not considered any specific bandwidth for this work. However the
authors in [13] demonstrate that the Lorenz signal is essentially narrowband
in nature. Hence, the effect of fading can be taken into account by
multiplying the first and second terms of $\eta_{\rm SL}$ in (8) with the
second and fourth (raw) moments of the channel fading gain [7], respectively.
Proposition 3 provides a generalized closed-form expression for the harvested
energy in terms of the scaling parameters333The energy transfer model
considered in this work is based on the assumption that the harvester operates
in the nonlinear region [2]. If the power of the harvester input signal
becomes too large, the diode inside the harvester is forced into the
saturation region of operation, making the derived analytical results
inapplicable.. The harvested DC $\eta_{\rm SL}$ corresponding to an ideal
scenario, i.e. $\epsilon_{x}\\!=\\!\epsilon_{y}\\!=\\!\epsilon_{z}\rightarrow
1$, can also be obtained as a special case, given in the following corollary.

######  Corollary 1.

In an ideal scenario, $\eta_{\rm SL}$ is given by

$\eta_{\rm L}=\rho_{1}\beta(r-1)+\rho_{2}\beta^{2}(r-1)^{2}.$ (9)

The above corollary follows directly from Proposition 3, by considering
$\epsilon_{x}\rightarrow 1$. Techniques such as predistortion [14] enable to
overcome the HPA imperfections, which further enhances the WPT performance.

Figure 2: Effect of scaling parameter on WPT performance; lines correspond to
analysis and markers correspond to simulation results.

Note that, we obtain closed-form expressions of the harvested DC for the
stable operation region of the scaled Lorenz attractor circuit. However, for
$r\notin\left(1,\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}\right)$, i.e. in
case of an unstable Lorenz system, (5) does not converge to any specific
point. As a result, it is not possible to analytically characterize the
harvested energy for this region of operation.

Even though the above analytical results are based on the Lorenz system, the
provided framework is general. Irrespective of the system, what is required is
the set of equilibrium points and the corresponding stability region. To show
this, we provide in the next section, how the approach can be extended to the
Hénon system [11].

###  III-C Extension to other multi-dimensional chaotic waveforms

The approach already presented to analytically characterize the harvested
energy is general and can be applied to any chaotic system. For the sake of
completeness, we consider another chaotic system, i.e. the Hénon map. A
conventional Hénon map is defined by the following first-order difference
equations [11]

$\displaystyle x_{n+1}$ $\displaystyle=y_{n}+1-\gamma x_{n}^{2},$ (10a)
$\displaystyle y_{n+1}$ $\displaystyle=\delta x_{n},$ (10b)

where $x,y$ are state variables and $\gamma,\delta$ are control parameters.
Note that, unlike the Lorenz system, a typical Hénon map is governed by two
state variables. Following an identical approach as before, we obtain the
corresponding stable equilibrium points as

$\displaystyle p_{\rm henon}$
$\displaystyle=\left(\left(\frac{\delta-1+\sqrt{(1-\delta)^{2}+4\gamma}}{2\gamma}\right)\right.,$
$\displaystyle\qquad\left.\delta\left(\frac{\delta-1+\sqrt{(1-\delta)^{2}+4\gamma}}{2\gamma}\right)\right),$
(11)

with $0<\delta<1,$ $\gamma\neq 0,$ and
$\displaystyle\gamma\in\left(-\frac{1}{4}(1-\delta)^{2},\frac{3}{4}(1-\delta)^{2}\right)$.
As a result, the harvested DC in this case is obtained as

$\eta_{\rm H}=\rho_{1}\Phi^{2}+\rho_{2}\Phi^{4},$ (12)

where $\Phi=\frac{\delta-1+\sqrt{(1-\delta)^{2}+4\gamma}}{2\gamma}$. Moreover,
if we consider a scaled Hénon system to accommodate the HPA imperfections, a
transformation of variables as described in (4) is required, and the
equilibrium point and the stability region changes accordingly. As was in the
case of a Lorenz system, it is not possible to analytically characterize the
harvested energy for an unstable Hénon system. Finally, we observe from (9)
and (12), it is possible to obtain $\eta_{\rm L}>\eta_{\rm H}$, only when

$\sqrt{\beta(r-1)}>\frac{\delta-1+\sqrt{(1-\delta)^{2}+4\gamma}}{2\gamma}.$
(13)

##  IV Numerical Results

We consider a transmission power $P_{t}=30$ dBm, transmitter-receiver distance
$d=20$ m, pathloss exponent $\alpha=4$, and system parameters $\sigma=10$ and
$\beta=8/3$. This implies that the system is stable as long as
$1<r<\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}=24.74$. Note that we can
also consider any other value of $\sigma$ and $\beta$, which accordingly gets
reflected in the range of $r$, as stated in Proposition 2, to have a stable
system. Finally, the parameters considered for the WPT model are
$k_{2}\\!=\\!0.0034,k_{4}\\!=\\!0.3829,$ and $R_{ant}\\!=\\!50$ $\Omega$,
respectively [2]. In addition, all the presented results are accompanied by
Monte Carlo simulations by using $10^{6}$ realizations.

Fig. 2 demonstrates the effect of $r$ and scaling parameters
$\epsilon_{x}=\epsilon_{y}=\epsilon_{z}=\epsilon$ on the WPT performance with
initial point $p_{\rm in}=(4,-10,0.6)$. We observe that the theoretical
results (lines) match very closely with the simulation results (markers); this
verifies our proposed analytical framework. The figure illustrates that the
harvested DC increases with $r$, which can not be indefinitely increased due
to the stability aspect. Furthermore, the figure also demonstrates the effect
of $\epsilon$ on the EH performance of the receiver. We observe that
$\epsilon$ strongly affects the EH performance, when all the other system
parameters remain constant. Recall that the scaling parameter depends on the
practical imperfections of the HPA at the transmitter. This implies that if we
are able to overcome the HPA imperfections, it enhances the harvested DC under
identical scenarios.

(a) Effect on PAPR.

(b) Effect on harvested energy.

Figure 3: WPT performance for unstable system with $p_{\rm in}=(0.1,10,0.1)$.

Note that the analytical expressions derived for the harvested DC correspond
to the stable region of operation for the Lorenz system. However, when the
Lorenz system operates in the unstable region, i.e.
$r>\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}=24.74$, the system does not
converge to any particular value and as a result, analytical closed-form
expressions can not be derived. We observe from Fig. 3(a) that the PAPR of the
signal at the receiver increases with $r$. Moreover, similar to [4], Fig. 3(b)
illustrates that the harvested DC increases with PAPR. It is worthy to note
that while the scaling
($\epsilon_{x}\\!=\\!\epsilon_{y}\\!=\\!\epsilon_{z}\\!=\\!6$ in the figure)
does not significantly affect the Lorenz system in terms of PAPR of the signal
at the receiver, there is a considerable gap in the WPT performance of the
scaled and unscaled Lorenz system. This detrimental effect of scaling on the
WPT performance justifies Proposition $3$ and the insights obtained
thereafter. Moreover, the figure also illustrates that unlike to the stable
scenario, $\sigma$ has an impact on both the PAPR and WPT performance of the
unstable Lorenz system. This particular observation leads to an interesting
conclusion, i.e. for multi-dimensional waveforms, high PAPR is not equivalent
to higher harvested energy and that the one-to-one PAPR-harvested energy
mapping holds only when we are dealing with uni-dimensional signals.

By considering an ideal transmission scenario, i.e. unity scaling factor, Fig.
4 compares the WPT performance of the Lorenz and Hénon signal in their
respective stable region of operation, with the existing $N$-tone multisine
waveforms [2]. We observe that the harvested energy increases with increasing
$r$, as stated in Proposition 3, and also with increasing number of
multitones. Moreover, we also observe from the figure that any arbitrary
multi-dimensional chaotic waveform transmission does not guarantee enhanced
WPT performance; for example, the performance gap for the Hénon map at
$P_{t}=20$ dBm between $\gamma=0.2,\delta=0.1$ and $\gamma=0.001,\delta=0.9$.
Note that the values considered are solely for illustration. Our results
demonstrate that the selection of parameter values is equally important as the
choice of the chaotic waveform.

##  V Conclusion

In this paper, we focused on the effects of multi-dimensional chaotic signals
on WPT. We evaluated the performance of energy transfer for the Lorenz
waveform under both, stable and unstable regions of operation, in terms of its
parameters. Closed-form expressions for the average harvested energy were
analytically derived and it was observed from exhaustive simulations, that for
multi-dimensional chaotic signals, high PAPR is not the single criterion for
obtaining an enhanced energy transfer performance. As the proposed framework
is general in nature, we also illustrate its application with respect to a
Hénon chaotic system. Finally, we compare the Lorenz and the Hénon signal with
the multisine waveforms, where we observe that the choice of parameters for
the chaotic waveforms is crucial in terms of WPT. An immediate extension of
this work is to investigate the class of multi-dimensional chaotic signals in
a generalized frequency selective scenario.

Figure 4: Performance comparison.

##  Appendix A Proof of Proposition 1

By setting $\dot{x}_{\rm sc}(t)=\dot{y}_{\rm sc}(t)=0$[10] in (5), we obtain

$y_{\rm sc}(t)=\frac{\epsilon_{x}x_{\rm sc}}{\epsilon_{y}}\quad\text{and}\quad
z_{\rm sc}(t)=\frac{r-1}{\epsilon_{z}}.$ (14)

Similarly, by substituting $\dot{z}_{\rm sc}(t)=0$ in (5c) and combining with
(14), we have

$x_{\rm sc}(t)=\pm\frac{\sqrt{\\!\beta(r\\!-\\!1)}}{\epsilon_{x}},\>y_{\rm
sc}(t)=\pm\frac{\sqrt{\\!\beta(r\\!-\\!1)}}{\epsilon_{y}},\>z_{\rm
sc}(t)=\frac{r\\!-\\!1}{\epsilon_{z}}.$ (15)

Note that while (15) holds for $r>1$, the origin, i.e. $(0,0,0)$ is an
equilibrium point for all values of $\sigma,r,\beta$. Thus, based on (14) and
(15), we obtain the equilibrium points for all possible values of the control
parameters as

$\displaystyle p_{\rm sc}=$ $\displaystyle(0,0,0),$ (16a) $\displaystyle
p_{\rm sc}=$
$\displaystyle\left(\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},\frac{\sqrt{\beta(r-1)}}{\epsilon_{y}},\frac{r-1}{\epsilon_{z}}\right),$
(16b) $\displaystyle p_{\rm sc}=$
$\displaystyle\left(-\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},-\frac{\sqrt{\beta(r-1)}}{\epsilon_{y}},\frac{r-1}{\epsilon_{z}}\right).$
(16c)

##  Appendix B Proof of Proposition 2

We obtain the Jacobian matrix corresponding to (5) as [15]

$J_{\rm
sc}=\begin{bmatrix}-\sigma&\displaystyle\frac{\epsilon_{y}}{\epsilon_{x}}\sigma&0\\\
\displaystyle\frac{\epsilon_{x}}{\epsilon_{y}}(r-\epsilon_{z}z_{\rm
sc}(t))&-1&-\displaystyle\frac{\epsilon_{x}\epsilon_{z}}{\epsilon_{y}}x_{\rm
sc}(t)\\\ \displaystyle\frac{\epsilon_{x}\epsilon_{y}}{\epsilon_{z}}y_{\rm
sc}(t)&\displaystyle\frac{\epsilon_{x}\epsilon_{y}}{\epsilon_{z}}x_{\rm
sc}(t)&-\beta\end{bmatrix}.$ (17)

By replacing the equilibrium points given by

$P_{1}=\left(\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},\frac{\sqrt{\beta(r-1)}}{\epsilon_{y}},\frac{r-1}{\epsilon_{z}}\right),$
(18) $\text{and}\quad
P_{2}=\left(-\frac{\sqrt{\beta(r-1)}}{\epsilon_{x}},-\frac{\sqrt{\beta(r-1)}}{\epsilon_{y}},\frac{r-1}{\epsilon_{z}}\right),$
(19)

in (17), we obtain

$J_{\rm
sc}^{(1)}\\!\\!=\\!\\!\begin{bmatrix}-\sigma&\displaystyle\frac{\epsilon_{y}}{\epsilon_{x}}\sigma&0\\\
\displaystyle\frac{\epsilon_{x}}{\epsilon_{y}}&-1&-\displaystyle\frac{\epsilon_{z}}{\epsilon_{y}}\sqrt{\beta(r-1)}\\\
\displaystyle\frac{\epsilon_{x}}{\epsilon_{z}}\sqrt{\beta(r-1)}&\displaystyle\frac{\epsilon_{y}}{\epsilon_{z}}\sqrt{\beta(r-1)}&-\beta\end{bmatrix},$
(20)

and

$J_{\rm
sc}^{(2)}\\!\\!=\\!\\!\begin{bmatrix}-\sigma&\displaystyle\frac{\epsilon_{y}}{\epsilon_{x}}\sigma&0\\\
\displaystyle\frac{\epsilon_{x}}{\epsilon_{y}}&-1&\displaystyle\frac{\epsilon_{z}}{\epsilon_{y}}\sqrt{\beta(r-1)}\\\
\displaystyle\frac{-\epsilon_{x}}{\epsilon_{z}}\sqrt{\beta(r-1)}&\displaystyle\frac{-\epsilon_{y}}{\epsilon_{z}}\sqrt{\beta(r-1)}&-\beta\end{bmatrix},$
(21)

respectively. It is interesting to observe that the eigenvalues of both (20)
and (21) are the roots of

$\lambda^{3}+\lambda^{2}(\sigma+\beta+1)+\lambda\beta(\sigma+r)+2\sigma\beta(r-1)=0.$
(22)

According to the Hurwitz stability criterion [16], the system is stable, if
and only if, all the principal diagonal minors of

$H=\begin{bmatrix}\sigma+\beta+1&2\sigma\beta(r-1)&0\\\ 1&\beta(\sigma+r)&0\\\
0&\sigma+\beta+1&2\sigma\beta(r-1)\end{bmatrix},$ (23)

are positive, which gives

$(\sigma+\beta+1)\beta(\sigma+r)>2\sigma\beta(r-1)\implies
r<\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}.$ (24)

Moreover, we also observe from (1) that $\sigma,\beta,r$ are positive
quantities, i.e. the inequality $\sigma>\beta+1$ must also be satisfied. This
completes the proof.

##  Appendix C Proof of Proposition 3

As stated in Section III-A, in the steady state, the system attains $P_{1}$ or
$P_{2}$ ( obtained in Appendix B), irrespective of the initial point $p_{\rm
in}$. Note that for both $P_{1}$ and $P_{2}$, we have

$\displaystyle\lim_{t\rightarrow\infty}\mathbb{E}\\{|x_{\rm sc}|(t)^{2}\\}$
$\displaystyle=\frac{\beta(r-1)}{\epsilon_{x}^{2}},$
$\displaystyle\text{and}\quad\lim_{t\rightarrow\infty}\mathbb{E}\\{|x_{\rm
sc}(t)|^{4}\\}$ $\displaystyle=\frac{\beta^{2}(r-1)^{2}}{\epsilon_{x}^{4}}.$
(25)

From Proposition 2, when the system is stable, i.e.
$r\in\left(1,\frac{\sigma(\sigma+\beta+3)}{\sigma-\beta-1}\right)$,
irrespective of $p_{\rm in}$, the harvested DC is

$\displaystyle\eta_{\rm SL}$
$\displaystyle=\lim_{t\rightarrow\infty}\rho_{1}\mathbb{E}\\{|x_{\rm
sc}(t)|^{2}\\}+\lim_{t\rightarrow\infty}\rho_{2}\mathbb{E}\\{|x_{\rm
sc}(t)|^{4}\\}$
$\displaystyle=\frac{\rho_{1}\beta(r-1)}{\epsilon_{x}^{2}}+\frac{\rho_{2}\beta^{2}(r-1)^{2}}{\epsilon_{x}^{4}},$
(26)

which follows from (C).

## References

  * [1] N. Shinohara, “Trends in wireless power transfer: WPT technology for energy harvesting, millimeter-wave/THz rectennas, MIMO-WPT, and advances in near-field WPT applications,” _IEEE Microwave Mag._ , vol. 22, no. 1, pp. 46–59, Jan. 2021.
  * [2] B. Clerckx and E. Bayguzina, “Waveform design for wireless power transfer,” _IEEE Trans. Signal Process._ , vol. 64, no. 23, pp. 6313–6328, Dec. 2016.
  * [3] N. Pan, D. Belo, M. Rajabi, D. Schreurs, N. B. Carvalho, and S. Pollin, “Bandwidth analysis of RF-DC converters under multisine excitation,” _IEEE Trans. Microw. Theory Techn._ , vol. 66, no. 2, pp. 791–802, Feb. 2018.
  * [4] D. I. Kim, J. H. Moon, and J. J. Park, “New SWIPT using PAPR: How it works,” _IEEE Wireless Commun. Lett._ , vol. 5, no. 6, pp. 672–675, Dec. 2016.
  * [5] A. Collado and A. Georgiadis, “Improving wireless power transmission efficiency using chaotic waveforms,” in _Proc. IEEE Int. Microw. Symp. Dig._ , Montreal, QC, Canada, Aug. 2012, pp. 1–3.
  * [6] ——, “Optimal waveforms for efficient wireless power transmission,” _IEEE Microw. Wireless Compon. Lett._ , vol. 24, no. 5, pp. 354–356, May 2014\.
  * [7] P. Mukherjee, C. Psomas, and I. Krikidis, “Differential chaos shift keying-based wireless power transfer with nonlinearities,” _IEEE J. Sel. Topics Signal Process._ , 2021, to appear.
  * [8] E. N. Lorenz, “Deterministic nonperiodic flow,” _J. Atmospheric Sci._ , vol. 20, no. 2, pp. 130–141, Mar. 1963.
  * [9] K. M. Cuomo, A. V. Oppenheim, and S. H. Strogatz, “Synchronization of Lorenz-based chaotic circuits with applications to communications,” _IEEE Trans. Circuits Syst. II. Analog Digit. Signal Process._ , vol. 40, no. 10, pp. 626–633, Oct. 1993.
  * [10] L. A. Sanchez, “Convergence to equilibria in the Lorenz system via monotone methods,” _J. Differ. Equ._ , vol. 217, no. 2, pp. 341–362, 2005.
  * [11] M. Hénon, “A two-dimensional mapping with a strange attractor,” _Commun. Math. Phys._ , vol. 50, no. 1, p. 69–77, Feb. 1976.
  * [12] C. Sparrow, _The Lorenz Equations: Bifurcations, Chaos, and Strange Attractors_. Springer, 1982\.
  * [13] G. Alvarez, F. Montoya, M. Romera, and G. Pastor, “Breaking two secure communication systems based on chaotic masking,” _IEEE Trans. Circuits Syst., II, Exp. Briefs_ , vol. 51, no. 10, pp. 505–506, Oct. 2004.
  * [14] P. Mukherjee, S. Lajnef, and I. Krikidis, “MIMO SWIPT systems with power amplifier nonlinearities and memory effects,” _IEEE Wireless Commun. Lett._ , vol. 9, no. 12, pp. 2187–2191, Dec. 2020.
  * [15] A. Papoulis and S. U. Pillai, _Probability, Random Variables, and Stochastic Processes_. McGraw-Hill Higher Education, 2002.
  * [16] B. A. Asner Jr., “On the total nonnegativity of the Hurwitz matrix,” _SIAM J. Appl. Math._ , vol. 18, no. 2, pp. 407–414, Mar. 1970.


# Stochastic Consensus and the Shadow of Doubt

Emilien Macault†,‡ † LEMMA, Université Paris 2 Panthéon-Assas, 16 rue Blaise
Desgoffes, 75006 Paris, France  ‡ HEC Paris, 1 Rue de la Libération, 78350
Jouy-en-Josas, France<EMAIL_ADDRESS>
###### Abstract.

We propose a stochastic model of opinion exchange in networks. Consider a
finite set of agents organized in a fixed network structure. There is a binary
state of the world and, ex ante, each agent is informed either about the true
state of the world with probability $\alpha$ or about the wrong state with
probability $1-\alpha$. We model beliefs as urns where white balls represent
the true state and black balls the wrong state. Communication happens in
discrete time and, at each period, agents draw and display one ball from their
urn with replacement. Then, they reinforce their urns by adding balls of the
colors drawn by their neighbors. We show that this process converges almost-
surely to a stable state where all urns have the same proportion of balls. We
show that this limit proportion is a random variable with full support over
$\left[0,1\right]$. We propose a conjecture on the distribution of this limit
proportion based on simulations.

Keywords. Reinforcement learning, opinion formation, consensus, non-Bayesian
learning, stochastic approximation.

##  1\. Introduction

Despite public investments in media education and the development of counter-
measures over the past few years, misinformation remains an ongoing issue with
tangible consequences. The recent examples of the COVID-19 pandemics or the US
presidential elections have highlighted how quickly inaccurate, deceptive or
politically biased information spreads in a context of distrust towards
experts and institutions.

Under pressure to limit the spread of deceptive content, media and open web
companies have put in place a set of policies to regulate news contents on
their platforms. Such policies mostly include source highlighting, fact
checking and advertisement campaigns, all of which have proved to have a
limited efficiency. The failure of counter-disinformation policies may be
explained by theoretical modeling shortcomings. Indeed, most policies are
based on the assumption that agents behave rationally when it comes to
information processing. By displaying the limited trustworthiness level of a
spurious source, they assume agents will revise their beliefs over secure
sources and naturally evacuate false news. In terms of economic modeling, this
translates into the assumption that agents behave in a Bayesian manner. In a
multi-agent context, the computational limitations of Bayesian models have
incentivized the emergence of non-Bayesian models as an alternative. Most of
these models are based on DeGroot, (1974) and consist in setups where agents
communicate by repeatedly averaging their opinions with their neighbors’ until
a steady state is reached. The strength of this framework is that beliefs
quickly converge to a tractable limit.

Yet, two major limitations are to be opposed to models based on DeGroot
dynamics. First, they have been shown to have limited robustness, in the sense
that the repeated averaging overweights initial beliefs while enforcing fast
convergence of beliefs. Second, one may question the relevance of a setup
where agents directly access and exchange their beliefs on some state. In most
small-world communication setups, it seems more realistic to assume that
agents do not access the subjective probabilities they put on the possible
values of a state, but rather decide to relay some information over another
according to the relative probabilities they put on those events. In other
terms, they do not exchange beliefs but draws based on beliefs. In this paper,
we introduce and analyze a stochastic variant of DeGroot dynamics where agents
behave in this respect.

Introducing some degree of stochasticity strongly changes the perspective on
misinformation: in DeGroot, (1974), slightly modifying the prior beliefs of
some agents cannot change drastically the consensus outcome. Yet, most
disinformation platforms display some "shadow of doubt" strategy: agents do
not transmit false informations because they necessarily believe them to be
true, but rather because there is some – even small – probability that they
may not be false. In other words, they manage to disinform by inducing limited
beliefs on their false informations.

###  1.1. Contribution

In this paper, we build an opinion formation model where agents communicate by
drawing states according to their beliefs instead of directly communicating
subjective probabilities. To do so, we model beliefs using reinforcing urns.
Studying the evolution of beliefs comes down to characterizing the evolution
of urns’ compositions. Using stochastic approximation techniques, we show that
in such models, under very general conditions, the dynamics of beliefs
converge to a rest point. We show that at the steady-state, all agents share
the exact same belief on the state of the world. As long as initial beliefs
cover the whole state space, the consensus is drawn from a distribution with
full support. This strongly contradicts the predictions of DeGroot’s and
similar models. We then try to characterize this limit distribution using
simulations.

###  1.2. Literature

The emergence of consensus and its connection to learning heuristics is a long
lasting question in theoretical economics. Two approaches are generally
opposed to this problem: Bayesian and non-Bayesian models.

Bayesian models on the emergence of consensus mostly started with Aumann,
(1976) and its seminal result that two agents with equal prior beliefs and
common knowledge posteriors must have equal beliefs. Generalizations have been
proposed by Geanakoplos and Polemarchakis, (1982) and Parikh and Krasucki,
(1990) who showed respectively that two players repeatedly communicating must
agree in the long run and that a finite umber of players communicating in
pairs will eventually agree. This is partly due to actions being observable,
although Bala and Goyal, (1998) proves that when agents are embedded in a
connected network and observe the outcome of their actions with some noise,
players are able to learn the true payoff distributions for actions that their
neighbors take infinitely often, hence all actions converge to a consensual
action. It is worth noting that although Bala and Goyal, (1998)considers
Bayesian agents, they limit their ability to compute beliefs by assuming that
they do not make inferences on unobserved players and behave myopically. These
results are closely related to social learning models and the observational
learning literature as Banerjee, (1992), Smith and Sørensen, (2000) or
Rosenberg et al., (2009). Mossel et al., (2020) generalizes those results to a
large class of social learning models by introducing the concept of _social
learning equilibrium_ to study the asymptotic properties of learning processes
and characterize conditions that agreement and herding behavior. In the same
line, Acemoglu et al., (2011) and Acemoglu et al., (2014) connect the
emergence of social learning with Bayesian agents and the topology of the
communication network.

Non-Bayesian consensus models emerged through DeGroot, (1974), where the
author introduces a model where agents living in a network repeatedly exchange
their beliefs over some state of the world. At each stage, each agent replaces
his belief by the average of his neighbors’ beliefs. It is shown that if the
communication network is connected, beliefs converge to a consensus which
depends on initial beliefs and the network topology only. Variations on the
updating rule have been proposed, for instance in Friedkin and Johnsen, (1997)
where authors allow some persistence on agents beliefs by including one’s own
belief in the averaging process. DeGroot’s model gained popularity with Golub
and Jackson, (2010) which connects consensus and learning with the network’s
adjacency matrix using properties of Markov chains steady-states. They refer
to DeGroot’s belief averaging dynamics as _naive learning_. Examples of the
use of DeGroot, (1974) in economic modeling are too numerous to be listed. In
the recent literature, Mandel and Venel, (2020) considers a stochastic game
where two misinformers try to influence a population of agents applying naive
learning. We refer the reader to Acemoglu and Ozdaglar, (2011) and Golub and
Sadler, (2017) for surveys on both Bayesian and non-Bayesian learning in
networks.

In this paper, we question the limits of DeGroot’s model by allowing agents to
communicate via draws made according to their beliefs. In this regard, this
work is in line with the existing literature on robustness of learning
dynamics. Acemoglu et al., (2016) questions the predictions of Bayesian
learning models by introducing uncertainty on the distribution of private
signals agents receive. Criticism on DeGroot dynamics already featured in
Golub and Jackson, (2010) where authors proved that in the general case,
beliefs do not converge for countably infinite player sets. In a recent work,
Peretz et al., (2021) shows that in the presence of agents with fixed beliefs
over time, which they call _bots_ , the common limit can converge to any
value.

Our approach to this problem is based on the seminal Polya urn model from
Eggenberger and Pólya, (1923). In this paper, authors consider an urn with
balls of several colors and study the convergence of reinforcement dynamics.
It is a well known result that proportions in the urn converge to a beta
distribution (see Klenke, (2013) for instance). The strength of Polya’s model
is its intricate connection with exchangeability. Central papers in the
foundation of Bayesian inference like De Finetti, (1929) and Hewitt and
Savage, (1955) heavily rely on the concept of exchangeability. Polya urn plays
a particular role in that Hill et al., (1987) proved that any exchangeable
process of $\left\\{0,1\right\\}$-valued random variables if either Bernoulli,
deterministic or generated by draws from a Polya urn. Our model considers a
system of interacting urns in the flavor of Paganoni and Secchi, (2004) which
introduced such systems and first proved convergence when the number of balls
in all urns grow at the same speed. Similarly, Dai Pra et al., (2014) shows
convergence of proportions in a system where urn reinforcement depends both on
proportions in each urn and on the average proportions in the system. Crimaldi
et al., (2016) gives further results on convergence and fluctuations around
the limit of such system. The model we consider is close yet different, as we
consider a system where urns are reinforced at different speeds which
correspond to their degree in the communication network. Usual probabilistic
tools do not apply as proportions are not martingales and draws are not
exchangeable. Instead, we rely on stochastic approximation as introduced by
Robbins and Monro, (1951). Motivation for the use of stochastic approximation
in the study of urn systems can be found in Laruelle et al., (2013), where
authors use this technique in the context of clinical trial modelling.

##  2\. The Model

###  2.1. Model

We consider a finite population $V=\left\\{1,\dots N\right\\}$ of $N$ agents,
embedded in a exogeneous and fixed undirected graph $G=(V,E)$ with edge set
$E$. We denote by $N(i)$ the neighborhood of any player $i$ and $d_{i}$ the
degree of $i$. We denote by $A=(a_{ij})_{i,j\in N}$ the adjacency matrix of
$G$, with the convention that $a_{ii}=0$ for all $i\in V$. Throughout, we will
assume that $G$ is _connected_ that is, for every pair of nodes $i,j$ in $E$
there exists a path in $G$ connecting $i$ to $j$.

We consider a binary state space $\Theta=\\{g,b\\}$. At the beginning of the
game, a state $\theta$ is drawn at random from $\Theta$ and is unobserved.
Players initially receive a noisy signal informing them about the state of the
world. Formally, with $\tilde{\theta}$ being the realized value of the state,
player $i$ receives a signal

$\begin{cases}\theta=\tilde{\theta}\text{ with probability }\alpha\\\
\theta=\tilde{\theta}^{c}\text{ with probability }1-\alpha\end{cases}$

With $\tilde{\theta}^{c}$ representing the complementary value of
$\tilde{\theta}$ in $\Theta$. For a large network, by the law of large
numbers, $\alpha$ represents the average proportion of agents initially well-
informed.

###  2.2. Beliefs and communication

We model beliefs using urns of infinite capacity with balls of two colors
representing the possible values of the state $\theta$: white balls represent
the event $\theta=\tilde{\theta}$ and black balls represent the complementary
event. At any time $t\geq 1$, the proportions of balls in agent $i$’s urn then
represent $i$’s belief over those two events. Urns are initialized with a ball
corresponding to the agent’s signal.

We define the communication process as a discrete time dynamics. At each
stage, players draw one ball with replacement from their urns with uniform
probability. Draws are assumed to be pairwise independent. Every agent
observes the colors drawn by their neighbors. Then, beliefs are updated by
reinforcing urns, adding one ball of the corresponding color for each draw
from their neighbors. The process is repeated infinitely.

At any given time, an agent’s current belief on $\theta$ is given by the
proportions of balls in his urn. Our objective is to study the evolution of
the urn system and determine whether proportions converge, if a consensus is
reached and if so, to characterize it given the network topology and the value
of $\alpha$.

###  2.3. Example

Consider $N=3$ agents connected in line as displayed in Fig. 1. Assume that at
time $t=0$, agent 1 and 3 received a truthful signal and agent 2 got the wrong
one. Then urns 1 and 3 will contain a white ball and urn 2 will contain one
blackball. At time $t=1$, every player draws the only ball their urns contain
and display it. Then, they all replace their draw and add a new ball of the
corresponding color for every draw they observe. That is, at the end of the
first stage, urns 1 and 3 will contain each one black ball and one white ball,
and urn 2 will contain one black ball and two white balls.

$1$$2$$3$ Figure 1.  Three urns in line.

At time $t=2$, the draw and reinforcement procedure is repeated: the end urns
will draw one black or one white ball with equal probability and the middle
urn will draw one white ball with probability $2/3$ and a black ball with
probability $1/3$.

Vector of draws | Probability of occurence | Urns compositions
---|---|---
(W,W,W) | 1/6 | (2,1)–(4,1)–(2,1)
(W,B,W) | 1/12 | (1,2)–(4,1)–(1,2)
(B,W,W) | 1/6 | (2,1)–(3,2)–(2,1)
(B,B,W) | 1/12 | (1,2)–(3,2)–(1,2)
(W,W,B) | 1/6 | (2,1)–(3,2)–(2,1)
(W,B,B) | 1/12 | (1,2)–(3,2)–(1,2)
(B,W,B) | 1/6 | (2,1)–(1,4)–(2,1)
(B,B,B) | 1/12 | (1,2)–(1,4)–(1,2)
Table 1. Possible outcomes at time $t=2$.

Table 1 details the possible outcomes at time $t=2$. The left column is the
vector of draws from urn 1, 2 and 3 respectively and the right column gives
the compositions at the end of the time period in the same order. Left figures
correspond to the number of white balls in the urn and right figures to the
number of black balls.

##  3\. Results

###  3.1. Urn dynamics

To ease the characterization of the dynamics, we introduce some notations.
First, denote by $B_{i}^{t}$ and $W_{i}^{t}$ respectively the numbers of white
and black balls in player $i$’s urn at time $t$. Define
$S_{i}^{t}=B_{i}^{t}+W_{i}^{t}$ the total number of balls in player $i$’s urn
at time $t$. One has that $S_{i}^{t+1}=S_{i}^{t}+d_{i}$ and $S_{i}^{0}=1$
hence $S_{i}^{t}1+d_{i}t$. Let $Z_{i}^{t}=B_{i}^{t}/S_{i}^{t}$ be the
proportion of black balls in urn $i$ after step $t$ and
$Z^{t}=(Z_{i}^{t})_{i\in V}$. Finally, let $X_{i}^{t}$ be the indicator
variable of a black draw for agent $i$ at time $t$,
$X^{t}=(X_{1}^{t},\dots,X_{N}^{t})$ and let $\mathcal{F}_{t}$ be the sigma-
field generated by the realizations of $(X^{k}),k\leq t$.

We derive the following dynamics:

$\begin{cases}B_{i}^{t+1}=B_{i}^{t}+\sum_{j\in N(i)}X_{j}^{t+1}\\\
W_{i}^{t+1}=W_{i}^{t}+d_{i}-\sum_{j\in N(i)}X_{j}^{t+1}\\\
S_{i}^{t+1}=S_{i}^{t}+d_{i}=1+d_{i}(t+1)\end{cases}$ (3.1)

Hence

$\mathbb{E}\left[\Delta
B_{i}^{t}|\mathcal{F}_{t}\right]=\mathbb{E}\left[\sum_{j\in
N(i)}X_{j}^{t+1}|\mathcal{F}_{t}\right]=\sum_{j\in N(i)}Z_{j}^{t}$ (3.2)

Eq. 3.2 shows that, in expectation, the belief updating process obeys some
local averaging property as in canonical naive learning models: the variation
of proportion in any urn evolves according to the proportions in the
neighboring urns.

###  3.2. Convergence of beliefs

We first show that beliefs converge in the sense that color proportions in
each urn converge to a stable point. The proof relies on stochastic
approximation techniques, as usual probability methods do not apply in our
case. Indeed, unless the graph $G$ is regular, neither local nor global
proportions behave as martingales and it is easy to see that the process
$(Z^{t})$ is not exchangeable as the rate at which an urns evolve depends both
its degree and time. Nevertheless, we are able to frame the dynamics as an
algorithm for which we can prove convergence.

######  Theorem 1.

For any graph $G$, $\lim_{t\rightarrow\infty}Z_{i}^{t}$ exists almost-surely
for any $i\in V$.

###### Proof.

From Eq. 3.1 we derive the following recursive formula on $Z_{i}^{t}$:

$Z_{i}^{t+1}-Z_{i}^{t}=\cfrac{-d_{i}Z_{i}^{t}+\sum_{j\in
N(i)}X_{j}^{t+1}}{1+d_{i}(t+1)}$ (3.3)

By adding and subtracting the conditional expectation of the number of black
draws in neighboring urns to the numerator, we have:

$Z_{i}^{t+1}-Z_{i}^{t}=\cfrac{-d_{i}Z_{i}^{t}+\mathbb{E}\left[\sum_{j\in
N(i)}X_{j}^{t+1}|\mathcal{F}_{t}\right]+\sum_{j\in
N(i)}X_{j}^{t+1}-\mathbb{E}\left[\sum_{j\in
N(i)}X_{j}^{t+1}|\mathcal{F}_{t}\right]}{1+d_{i}(t+1)}$ (3.4)

Observing that, conditional on $\mathcal{F}_{t}$, the expected number of black
draws in neighboring urns at time $t+1$ is equal to the sum of their
proportions at time $t$, we obtain:

$Z_{i}^{t+1}-Z_{i}^{t}=\cfrac{-d_{i}Z_{i}^{t}+\sum_{j\in
N(i)}Z_{j}^{t}+\sum_{j\in N(i)}X_{j}^{t+1}-\mathbb{E}\left[\sum_{j\in
N(i)}X_{j}^{t+1}|\mathcal{F}_{t}\right]}{1+d_{i}(t+1)}$ (3.5)

We now rescale the equation by a factor that is independent of $d_{i}$:

$Z_{i}^{t+1}-Z_{i}^{t}=\cfrac{\cfrac{1+d(t+1)}{1+d_{i}(t+1)}\left(-d_{i}Z_{i}^{t}+\sum_{j\in
N(i)}Z_{j}^{t}+\sum_{j\in N(i)}X_{j}^{t+1}-\mathbb{E}\left[\sum_{j\in
N(i)}X_{j}^{t+1}|\mathcal{F}_{t}\right]\right)}{1+d(t+1)}$ (3.6)

Where $d=\min_{i}d_{i}$. Finally, we obtain the following system:

$Z^{t+1}-Z^{t}=\gamma^{t}\left[f^{t}(Z^{t})+u^{t}\right]$ (3.7)

Where

$\begin{cases}\gamma^{t}=\cfrac{1}{1+d(t+1)},\\\ \\\
f^{t}:\left[0,1\right]^{N}\to\left[0,1\right]^{N}\\\ \qquad\quad
Z^{t}\mapsto(f_{1}^{t}(Z^{t}),\dots,f_{N}^{t}(Z^{t}))\\\ \\\ \text{with
}f_{i}^{t}(Z^{t})=\cfrac{1+dt}{1+d_{i}t}\sum_{j\in
N(i)}Z_{j}^{t}-d_{i}Z_{i}^{t},\\\ \\\ u^{t}=(u_{1}^{t},\dots,u_{N}^{t}),\\\
\text{with }u_{i}^{t}=\cfrac{1+dt}{1+d_{i}t}\sum_{j\in
N(i)}X_{j}^{t+1}-\mathbb{E}\left[\sum_{j\in
N(i)}X_{j}^{t+1}|\mathcal{F}_{t}\right]\end{cases}$ (3.8)

In order to ensure convergence of the stochastic system Eq. 3.7, we first make
the following observations.

######  Assumption 1.

$\begin{cases}\sum_{t=1}^{\infty}\gamma^{t}=\infty\\\
\sum_{t=1}^{\infty}\left(\gamma^{t}\right)^{2}<\infty\end{cases}$ (3.9)

Assumption 1 is central in any stochastic approximation algorithm à la Robbins
and Monro, (1951) with deterministic weights. These weights serve as the
increments of time discretization. In that perspective, the first point
implies that the algorithm will cover the entire time interval. The second
point involves, jointly with the next observation, the disappearing of noise
in the limit. As $\gamma^{t}$ is of the order of $1/t$, Assumption 1 is
immediate.

######  Assumption 2.

For every $i$ in $V$, the sequence $(u_{i}^{t})$ is a martingale difference
noise relative to $\mathcal{F}_{t}$.

Assumption 2, when combined with the second point in Assumption 1, ensures
that the cumulative error due to the discretization noise is negligible
almost-surely, as the noise variance will vanish asymptotically. Assumption 2
holds as, for any $i\in V$, the sequence $(u_{i}^{t})$ is a sequence of
bounded random variables with zero mean.

######  Assumption 3.

The maps $f_{i}^{t}$ are Lipschitz continuous and measurable with respect to
$\mathcal{F}_{t}$ and uniformly continuous in $t$ for $t\geq 1$.

Stochastic approximation ensures that a discrete-time stochastic process
evolves along the trajectories of a continuous time ordinary differential
equation. In that respect, Assumption 3 ensures that the ODE is well defined
and has a unique solution.

Finally, although the maps $(f_{i}^{t})_{i,t}$ in Eq. 3.7 depend on time, for
any $i\in V$, the sequence of maps $(f_{i}^{t})$ converge to a time-
independent limit as time goes to infinity. Indeed, for any $i\in V$ and any
$z\in\left[0,1\right]^{N}$, let $\bar{f}_{i}(z)=\frac{d}{d_{i}}\sum_{j\in
N(i)}z_{j}-d_{i}z_{i}$ and
$\bar{f}:z\mapsto\left(\bar{f}_{1}(z),\dots,\bar{f}_{N}(z)\right)$.

######  Assumption 4.

For any $z\in\left[0,1\right]^{N}$ and any $k\in\mathbb{N}^{*}$,

$\lim_{s\to\infty}\left|\sum_{t=s}^{s+k}\gamma^{t}\left[f_{i}^{t}(z)-\bar{f}_{i}(z)\right]\right|\to
0$

Assumption 4 holds immediately as, for any $i\in V$, $f_{i}^{t}\to\bar{f}_{i}$
as $t\to\infty$.

Based on Assumptions 1–4, we can apply Theorem 2.3 from Kushner and Yin,
(2003, chapter 5).

######  Theorem 2 (Kushner and Yin, (2003, chapter 5)).

If Assumptions 1–4 hold and $\left(Z^{t}\right)$ is bounded with probability
one, then for almost all $\omega$, the limits $\bar{Z}(\omega)$ of convergent
subsequences of $\left(Z^{t}(\omega)\right)$ are trajectories of

$\dot{z_{i}^{t}}=\bar{f}(z^{t})$ (3.10)

in some bounded invariant set and $\left(Z^{t}(\omega)\right)$ converges to
this invariant set.

This result ensures that the system Eq. 3.7 evolves almost-surely along
trajectories of Eq. 3.10 and converges to the set of asymptotically stable
points of the ordinary differential system.

∎

This first result ensures that for any graph structure $G$ and any initial
condition on the urns, proportions converge almost-surely to a stable point.
In particular, convergence is independent of the initial signal structure and
applies for any alternative initialization of the system. The next result
details when a consensus emerges.

###  3.3. Emergence of Consensus

######  Theorem 3.

Suppose that the graph $G$ is connected. Then for any $i,j\in V$,
$\lim_{t\rightarrow\infty}Z_{i}^{t}=\lim_{t\rightarrow\infty}Z_{j}^{t}$
almost-surely.

###### Proof.

From Theorem 4, we know that proportions converge along the trajectories of
Eq. 3.10, that is:

$\dot{z_{i}^{t}}=\cfrac{d}{d_{i}}\sum_{j\in N(i)}z_{j}^{t}-d_{i}z_{i}^{t}$
(3.11)

As $\frac{1}{N}\leq\frac{d}{d_{i}}\leq 1$, stable points of Eq. 3.10 belong to
the set of stable points of

$\dot{z_{i}^{t}}=\sum_{j\in N(i)}z_{j}^{t}-d_{i}z_{i}^{t}$ (3.12)

i.e.

$\dot{z}^{t}=-Lz^{t}$ (3.13)

Where $L$ is the Laplacian matrix of the graph $G$, i.e. $L=D-A$ with $D$ the
diagonal matrix of degrees.

Thus, Lyapounov stable solutions of Eq. 3.10 belong to the nullspace of $-L$,
as $L$ is symmetric, positive semi-definite. As $G$ is connected, this
nullspace is of dimension 1 and is characterized by the eigenvector
$(1,...,1)$ as the sum of each row in $L$ equals zero. As $-L$ is negative,
the entire set is Lyapounov stable.

∎

######  Theorem 4.

For any connected graph $G$, if $\alpha\in\left(0,1\right)$, then the limit
belief $\bar{Z}$ is a non-trivial distribution with full support on
$\left[0,1\right]$.

###### Proof.

The proof is based on the concept of _attainability_ from Benaïm, (1999).

######  Definition 5.

A point $p\in\mathbb{R}^{N}$ is _attainable_ by $Z$ if for every $t>0$ and
every open neighborhood $U$ of $p$,

$\mathbb{P}\left(\exists s\geq t:Z^{s}\in U\right)>0.$

In other terms, a point $p$ is attainable if, from any vector of proportions,
there is a strictly positive probability that $Z^{t}$ becomes arbitrarily
close to $p$ in finite time. Let $L_{\bar{f}}$ denote the set of equilibrium
points of Eq. 3.10 intersected with $\left[0,1\right]^{N}$ that is,
$L_{\bar{f}}=\left\\{z\in\left[0,1\right]|z_{i}=z_{j}\forall i,j\leq
N\right\\}$. We establish the following lemma.

######  Lemma 6.

Any point $p$ in $L_{\bar{f}}$ is attainable.

To prove Lemma 6, simply observe that, from Eq. 3.1, $Z_{i}^{t+1}-Z_{i}^{t}$
is of the order of $\frac{1}{t}$. If $\alpha\in\left(0,1\right)$,
$\mathbb{P}\left(Z_{i}^{t}\in\left(0,1\right)\right)>0$ for every $i$ and
$t\geq 0$.

We showed that any point in $L_{\bar{f}}$ is attainable. To complete the proof
of Theorem 4, it remains to show that any attainable point in $L_{\bar{f}}$
belongs to the support of $Z^{\infty}$.

∎

Observe that if $\alpha=0$ or $\alpha=1$, urns in the system display only one
color hence beliefs will remain at their original value forever.

The next section provides some empirical evidence on the limit distribution of
beliefs.

##  4\. Limit Distribution

While our efforts in characterizing the limit distribution of the consensus
$Z$ as a function of $G$ and $\alpha$ failed, large scale simulations provide
some useful evidence. We simulated the learning dynamics on three network
structures: stars, regular graphs with varying degree and complete networks.
The values of the limit belief were simulated for different values of
$\alpha$. Main elements of code used for the simulation feature in the
appendix.

###  4.1. Evidence of a Beta Distribution

In the classical model from Eggenberger and Pólya, (1923), an urn is
initialized at time $t=0$ with $\alpha\geq 1$ white balls and $\beta\geq 1$
black balls. Then, at each discrete time step, a ball is drawn from the urn
and replaced with $m\geq 1$ additional balls of the same color. It is
widespread that the proportion of white balls converges in distribution to a
beta distribution $\mathcal{B}(\alpha/m,\beta/m)$ (see Mahmoud, (2008)).

For any two reals $a,b>0$, the beta distribution $\mathcal{B}(a,b)$ has a
density function

$p(x,a,b)=\cfrac{x^{a-1}(1-x)^{b-1}}{B(a,b)}\mathbbm{1}_{\left\\{x\in\left[0,1\right]\right\\}}$
(4.1)

where $B(a,b)=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$ and $\Gamma$ is the
Gamma function.

Although we consider a system of interacting urns rather than a single urn,
the beta distribution stands as a strong candidate for the limit distribution.

Figure 2. Fitness measures for beta and normal distributions on a star graph
with $\alpha=0.75$, $n=5000$ observations.

######  Conjecture 7.

The distribution of $\bar{Z}$ follows a beta distribution $\mathcal{B}(a,b)$
for some $a,b,>0$ which depend only on $\alpha$ and $G$.

We collected the values of the limit belief for star, $k$-regular and complete
graphs of fixed size $N=100$ and fixed values of $\alpha$. As all the
simulations were run independently, for any given graph structure and value of
$\alpha$, the set of values of the limit beliefs is an i.i.d. sample. A beta
distribution fitting was computed by maximum likelihood estimation. Other
distributions were fitted in order to assess goodness-of-fit using usual
criteria. Fig. 2 compares the fitted distributions assuming respectively a
normal distribution and a beta distribution. The graph displays empirical and
theoretical densities, quantile-quantile plots, cumulative distribution
functions and probability plots. The beta distribution clearly appears as well
fitted to the sample. Additional plots feature in the appendix for different
network structures and values of $\alpha$. In all the aforementioned cases,
fitness measures yielded similar results, where the beta distribution clearly
appears as more adapted to describe the data.

###  4.2. Estimation of the Parameters

Assuming the limit belief does follow a beta distribution, we are able to
estimate its parameters using maximum likelihood estimation for various
networks and values of $\alpha$. Our first conjecture concerns the average of
the limit distribution. All the simulations we ran conducted to a strong
belief in that its value is $\alpha$. In other terms, the expected proportion
of black balls in the limit is equal to the expected number of misinformed
agents ex-ante.

######  Conjecture 8.

For any $i\in N$, $Z_{i}^{t}\to\bar{Z}$ where $\bar{Z}\sim\mathcal{B}(a,b)$
with $a,b>0$ such that $\frac{a}{a+b}=\alpha$.

To support this conjecture, we simulated the communication dynamics on a
$10$-regular network for increasing values of alpha and fitted a beta
distribution to the empirical distribution. Table 2 provides estimates of the
parameters and sample means.

$\alpha$ | $\hat{a}$ | $\hat{b}$ | $\hat{a}+\hat{b}$ | Empirical mean
---|---|---|---|---
0.1 | 6.09 | 54.63 | 60.72 | 0.100
0.2 | 11.9 | 47.6 | 59.5 | 0.199
0.3 | 18.3 | 42.7 | 61 | 0.300
0.4 | 24.8 | 37.2 | 62 | 0.399
0.5 | 30.8 | 30.8 | 61.6 | 0.499
0.6 | 37.4 | 24.9 | 62.3 | 0.601
0.7 | 43.1 | 18.5 | 61.5 | 0.699
0.8 | 48.4 | 12.1 | 60.5 | 0.8005
0.9 | 51.19 | 5.68 | 56.87 | 0.900
Table 2. Estimates $\hat{a}$ and $\hat{b}$ of $a$ and $b$ and empirical mean
in a $10$-regular network of size $N=100$ (14000 obs.).

Similar simulations for other network structures yield identical results.
These outputs strongly suggest that the belief updating dynamicsEq. 3.1 bear
some form of asymptotical exchangeability. It remains to be proved yet it
would strongly support 7. Finally, we observe consistency in the sum of the
estimates $\hat{a}$ and $\hat{b}$, which support the following conjecture.

######  Conjecture 9.

Fix a network $G$ and let $\bar{Z}_{\alpha}$ be the beta distribution of the
limit belief given $\alpha$. Let $a_{\alpha}$ and $b_{\alpha}$ be its
parameters. Then the mapping $\alpha\mapsto a_{\alpha}+b_{\alpha}$ is
constant.

To support this conjecture, we explored results from simulations on the three
aforementioned structures. We believe that discrepancies as observed in Table
2 are due to noise introduced by the random number generator as they mostly
appear for extreme values of $\alpha$.

##  5\. Future Work

Further work has been done in trying to characterize the limit distribution of
the consensus analytically, yet no method has yield convincing results so far.
Based on the simulations we ran, we have strong hints that suggest this limit
distribution is a beta distribution. This confirms the intuition that, as a
whole, the system acts as a global Polya urn. Further exploration of possible
exchangeability properties might help in supporting this intuition and provide
some tools for a closed-form characterization. To our knowledge, no paper has
been able to achieve such formal results on interacting urn systems.

A better understanding of the limit distribution would provide a better
applicability of our results, in particular in designing a model of strategic
disinformation with disinformants being parts of the network. That application
was the initial motivation of the paper and remains its main objective.

## References

  * Acemoglu et al., (2014) Acemoglu, D., Bimpikis, K., and Ozdaglar, A. (2014).  Dynamics of information exchange in endogenous social networks.  Theoretical Economics, 9(1):41–97.
  * Acemoglu et al., (2016) Acemoglu, D., Chernozhukov, V., and Yildiz, M. (2016).  Fragility of asymptotic agreement under bayesian learning.  Theoretical Economics, 11(1):187–225.
  * Acemoglu et al., (2011) Acemoglu, D., Dahleh, M. A., Lobel, I., and Ozdaglar, A. (2011).  Bayesian learning in social networks.  The Review of Economic Studies, 78(4):1201–1236.
  * Acemoglu and Ozdaglar, (2011) Acemoglu, D. and Ozdaglar, A. (2011).  Opinion dynamics and learning in social networks.  Dynamic Games and Applications, 1(1):3–49.
  * Aumann, (1976) Aumann, R. J. (1976).  Agreeing to disagree.  The annals of statistics, pages 1236–1239.
  * Bala and Goyal, (1998) Bala, V. and Goyal, S. (1998).  Learning from neighbours.  The review of economic studies, 65(3):595–621.
  * Banerjee, (1992) Banerjee, A. V. (1992).  A simple model of herd behavior.  The quarterly journal of economics, 107(3):797–817.
  * Benaïm, (1999) Benaïm, M. (1999).  Dynamics of stochastic approximation algorithms.  In Seminaire de probabilites XXXIII, pages 1–68. Springer.
  * Crimaldi et al., (2016) Crimaldi, I., Dai Pra, P., and Minelli, I. G. (2016).  Fluctuation theorems for synchronization of interacting pólya’s urns.  Stochastic processes and their applications, 126(3):930–947.
  * Dai Pra et al., (2014) Dai Pra, P., Louis, P.-Y., and Minelli, I. G. (2014).  Synchronization via interacting reinforcement.  Journal of Applied Probability, 51(2):556–568.
  * De Finetti, (1929) De Finetti, B. (1929).  Funzione caratteristica di un fenomeno aleatorio.  In Atti del Congresso Internazionale dei Matematici: Bologna del 3 al 10 de settembre di 1928, pages 179–190.
  * DeGroot, (1974) DeGroot, M. H. (1974).  Reaching a consensus.  Journal of the American Statistical Association, 69(345):118–121.
  * Eggenberger and Pólya, (1923) Eggenberger, F. and Pólya, G. (1923).  Über die statistik verketteter vorgänge.  ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 3(4):279–289.
  * Friedkin and Johnsen, (1997) Friedkin, N. E. and Johnsen, E. C. (1997).  Social positions in influence networks.  Social networks, 19(3):209–222.
  * Geanakoplos and Polemarchakis, (1982) Geanakoplos, J. D. and Polemarchakis, H. M. (1982).  We can’t disagree forever.  Journal of Economic theory, 28(1):192–200.
  * Golub and Jackson, (2010) Golub, B. and Jackson, M. O. (2010).  Naive learning in social networks and the wisdom of crowds.  American Economic Journal: Microeconomics, 2(1):112–49.
  * Golub and Sadler, (2017) Golub, B. and Sadler, E. (2017).  Learning in social networks.  Available at SSRN 2919146.
  * Hewitt and Savage, (1955) Hewitt, E. and Savage, L. J. (1955).  Symmetric measures on cartesian products.  Transactions of the American Mathematical Society, 80(2):470–501.
  * Hill et al., (1987) Hill, B. M., Lane, D., Sudderth, W., et al. (1987).  Exchangeable urn processes.  The Annals of Probability, 15(4):1586–1592.
  * Klenke, (2013) Klenke, A. (2013).  Probability theory: a comprehensive course.  Springer Science & Business Media.
  * Kushner and Yin, (2003) Kushner, H. and Yin, G. (2003).  Stochastic Approximation and Recursive Algorithms and Applications.  Stochastic Modelling and Applied Probability. Springer New York.
  * Laruelle et al., (2013) Laruelle, S., Pages, G., et al. (2013).  Randomized urn models revisited using stochastic approximation.  Annals of Applied Probability, 23(4):1409–1436.
  * Mahmoud, (2008) Mahmoud, H. (2008).  Pólya urn models.  CRC press.
  * Mandel and Venel, (2020) Mandel, A. and Venel, X. (2020).  Dynamic competition over social networks.  European Journal of Operational Research, 280(2):597–608.
  * Mossel et al., (2020) Mossel, E., Mueller-Frank, M., Sly, A., and Tamuz, O. (2020).  Social learning equilibria.  Econometrica, 88(3):1235–1267.
  * Paganoni and Secchi, (2004) Paganoni, A. M. and Secchi, P. (2004).  Interacting reinforced-urn systems.  Advances in applied probability, 36(3):791–804.
  * Parikh and Krasucki, (1990) Parikh, R. and Krasucki, P. (1990).  Communication, consensus, and knowledge.  Journal of Economic Theory, 52(1):178–189.
  * Peretz et al., (2021) Peretz, R., Amir, G., Arieli, I., and Ashkeazi-Golan, G. (2021).  Robust naive learning in social networks.  Working Paper.
  * Robbins and Monro, (1951) Robbins, H. and Monro, S. (1951).  A stochastic approximation method.  The annals of mathematical statistics, pages 400–407.
  * Rosenberg et al., (2009) Rosenberg, D., Solan, E., and Vieille, N. (2009).  Informational externalities and emergence of consensus.  Games and Economic Behavior, 66(2):979–994.
  * Smith and Sørensen, (2000) Smith, L. and Sørensen, P. (2000).  Pathological outcomes of observational learning.  Econometrica, 68(2):371–398.