Mutual Information and Multi-Agent Systems

Abstract

We consider the use of Shannon information theory, and its various entropic terms to aid in reaching optimal decisions that should be made in a multi-agent/Team scenario. The methods that we use are to model how various agents interact, including power allocation. Our metric for agents passing information are classical Shannon channel capacity. Our results are the mathematical theorems showing how combining agents influences the channel capacity.

1. Introduction

Advances in machine intelligence have led to an increase in human-agent teaming. In this context, one or more machines act as semi-autonomous or autonomous agents interacting with other machine teammates and/or their human proxies. This phenomenon has led to cooperative work models where the role of an agent can be, interchangeably, a human, or machine, support system. Human counterparts that interact with automation become less like operators, supervisors, or monitors, and more like equal-authority peers.

Critical to the success of any team is efficient and effective communication. Multi-agent systems are no different. Information sharing is a key element in building collective cognition, and it enables agents to cooperate and ultimately achieve shared goals successfully. Information sharing, or communication, provides the foundation for a team’s success. In complex multi-agent engagements, information is not always universally available to all agents. Such engagements are often characterized by distributed entities with limited communication channels among them, where no agent has a complete view of the solution space, and information relevant to team goals only becomes available to team members in spontaneous, unpredictable and even unanticipated ways. Moreover, there is always a resource cost to inter-agent communication. Finding highly efficient and effective communication patterns is a recurring problem in any multi-agent system, particularly if the system agents are distributed.

We are concerned with how a Multi-agent System (MAS) [1], or Team, sends information between agents or teammates. By “how” we mean “how” in an information theoretic [2] sense—in particular, we do not concentrate on the mechanics or physics of the transmission other than how it impacts information theory. We are concerned with what strategy an agent can to use to maximize its information flow to another agent. From an information geometric standpoint, we only use a simple metric in this article, but lay the ground work for more complex Riemannian metrics. We are concerned with a transmitting agent sending a small amount of distinct symbols in a fixed time. In fact, we restrict ourselves to two symbols to develop our theory (A list of notation is at the end of the article.). We are using a mathematical approach to model the communication between two agents. The equations we present are based on a series of assumptions that we will explain.

We assume that an agent sends two symbols to another agent. We refer to the symbols as “0” or “1”. We are concerned with the fidelity of how the symbols are passed. All symbols take the same time to pass. We will be looking at the (Shannon) capacity as one agent attempts to send a symbol to another agent.

Our scenario is illustrated in Figure 1 and Figure 2. The first agent $A_X$ sends a 0 or 1 to the second agent $A_Y$. We have a clock and the unit of time is t. Every t, $A_X$ transmits the symbol to $A_Y$. We assume that the symbol is received within the same time unit (i.e., we assume instantaneous transmission speeds during each interval t). There is no feedback (which, for the channels we analyze, would not change the capacity anyway (p. 520 [3])) from $A_Y$ to $A_X$, and the transmission is considered to be memoryless (quoting [4], “…channel is memoryless if the probability distribution of the output depends only on the input at that time and is conditionally independent of previous channel inputs or outputs”). Furthermore, it is implicit that the channel statistics never change (sometime the literature refers to this as a “stationary” condition).

To summarize the above, we have a Discrete Memoryless Channel (DMC) between $A_X$ and $A_Y$. This channel measures information flow in terms of bits per symbol (since t does not vary). We let X represent the input distribution to this DMC, and we let Y denote the output random variable.

The probability for the random variable X is given by $P(X=i),i=0,1$; it is the probability that $A_X$ inputs symbol i, and $P(Y=j),j=0,1$ is the probability that $A_Y$ received symbol j. The input distribution X is determined by the transmission fidelity of $A_X$. In particular,

$$x=P(X=0)=x,\overline{x}:=P(X=1)=1-x.$$

(1)

Whereas the output distribution Y is determined by the (assumed to be well-defined) conditional distribution between X and Y, and the input distribution. Thus,

$$P(Y=j)=\sum _{i}P(Y=j|X=i)·P(X=i).$$

(2)

The approach presented in this paper follows from [2,5,6,7].

The conditional probabilities of the DMC is given by a $2\times 2$ matrix $M_1$, where (Please keep in mind the swapping of the indices, and, as we had above for $\overline{x}$, that notationally $\overline{\ast }:=1-\ast$. Furthermore, the convention is that a conditional probability is fixed for all $P(X=i)$, even if that probability is 0. In the next footnote, we address the impact of this with respect to (w.r.t.) information theory).

$$m_{i,j}:=P(Y=j|X=i)\mathrm{and}$$

(3)

$$M_1=\left(\begin{array}{cc}{m}_{0,0}& m_{0,1}\\ m_{1,0}& m_{1,1}\end{array}\right)=\left(\begin{array}{cc}P(Y=0|X=0)& P(Y=1|X=0)\\ P(Y=0|X=1)& P(Y=1|X=1)\end{array}\right)=:\left(\begin{array}{cc}a& \overline{a}\\ b& \overline{b}\end{array}\right).$$

(4)

Note that $(a,b)\in [0,1]\times [0,1]$.

Before we continue with the mathematics let us put this research into some more perspective. Von Neumann’s [8] seminal work had no concept of “Teamwork”, which is at the core of what we are discussing. Sliwa’s [9] review suggests that minimum communication channels are more important when context is understood during teamwork, a suggestion opposite to our work in this article which we hope to test in the future. Lawless [10] suggests that maximized channels become more important when Teams confront uncertainty in their environment. Schölkopf et al. [11] suggest that i.i.d. data are insufficient to reconstruct whatever social event is being captured, that something is missing and a new approach must be innovated, our goal in this article. Our results will be discussed in situ for maximum effect.

1.1. Entropy and Mutual Information

We extend our random variables to allow more than two possible outcomes, and give the following definitions with the most generality possible. We now have $I+1$ possible inputs, and $J+1$ possible outcomes.

Given a discrete random variable V, we define the entropy of V as (By convention log is the base 2 logarithm, and ln is the natural logarithm. Furthermore, we are able to extend the definitions (p. 19 [4]), as is standard, so that $0log\left(0\right)=0log(0/0)=0$. These conventions allows the most general derivation of (8) from (7)).

$$H\left(V\right):=-\sum _{j}P(V=v_j)logP(V=v_j).$$

If $z\in [0,1]$, then we define the binary entropy function of z as

$$h\left(z\right):=-zlog\left(z\right)-(1-z)log(1-z).$$

Note that if B is a binary random variable taking the values 0 or 1, then $H\left(B\right)=h\left(P(B=0)\right)$. In fact, we simplify the notation and express the probability of the event $\{V=v_k\}$ as

$$p_v\left(v_k\right)=P(V=v_k).$$

Furthermore, when it is clear which distribution we are using, we further simplify the notation and just write $p\left(v_k\right)$. Thus,

$$H\left(B\right)=h\left(p\left(0\right)\right).$$

Given two discrete random variables $V,W$, we define [2] the conditional entropy of V given W as

$$\begin{array}{cc}\hfill H\left(V\right|W):=& -\sum _i{p}_w\left(w_i\right)\sum _j{p}_{v|w}\left(v_j\right|w_i)log{p}_{v|w}\left(v_j\right|w_i),\hfill \end{array}$$

(5)

where, as in the $2\times 2$ case

$$P\left(v_j\right|w_i):=m_{i,j},i=0,1,\dots ,I;j=0,1,\dots ,J,$$

forming the channel matrix (Of course, as in the 2 × 2 case, conditional probability is only defined when $p\left(w_i\right)\ne 0$. However, as we note below, such terms are dealt with by using the limiting value of the constant conditional probability term which makes our mutual information calculations consistent, keeping in mind that $0log\ast$ is always taken to be 0. Furthermore, keep in mind that a distribution that achieves capacity for a 2-input channel (the subject of this paper) never has either probability value as zero of course (Ref. [12] gives better bounds). There are, however, $3\times 2$ channels for which this does not hold, for example $\left(\begin{array}{cc}1& 0\\ 0.8& 0.2\\ 0& 1\end{array}\right)$ which has an optimizing input distribution of $(0.5,0,0.5)$.)

$$M=\left(\begin{array}{cccc}p\left(v_0\right|w_0)& p\left(v_1\right|w_0)& \dots & p\left(v_J\right|w_0)\\ p\left(v_0\right|w_1)& p\left(v_1\right|w_1)& \dots & p\left(v_J\right|w_1)\\ ⋮& ⋮& \ddots & ⋮\\ p\left(v_0\right|w_I)& p\left(v_1\right|w_I)& \dots & p\left(v_J\right|w_I)\end{array}\right).$$

(6)

We define the mutual information between V and W by [2]

$$I(V,W):=H\left(V\right)-H\left(V\right|W)=H(W)-H(W\left|V\right)=:I(W,V).$$

(7)

Using (5) and (7), and some substitutions [4] (again, division by 0 is taken care of in the usual way by using limiting values ([Section 2.3] [4]), we find that

$$I(V,W)=\sum _{j,i}p(v_j,w_i)log\left(\frac{p(v_j,w_i)}{p\left(v_j\right)p\left(w_i\right)}\right).$$

(8)

We now give Shannon’s definition [2] of (channel) capacity. It has been well-studied since its inception. We will not delve into the Noisy Coding Theorem, or any of the other results which showcase its importance. Rather, we will assume in this paper that capacity is a standard measure of how much information a channel can transmit in an essentially noise-free manner [2,4]. The traditional units of capacity and mutual information are accepted in this article; they are bits per channel usage, which in our scenario is equivalent to bits per t.

Definition 1.

We consider W to be the input random variable to a DMC. The capacity C of the DMC is

$$C:=\underset{\left\{p\left(w_i\right)\right\}}{sup}I(V,W).$$

(9)

The optimization is taken over all possible distributions of W with its fixed values $w_i$. The supremum is actually achieved and can be taken as a maximum [2,4]. Note that when trying to compare the magnitude of the channel capacity (with the same number of inputs), it suffices to compare the mutual information for all x values. Of course the two channels may have different optimizing distributions. Note the principle (and similar principles) that if $\forall x,I(C{H}_1,x)\le I(C{H}_2,x)$ and if $C{H}_1$ achieves capacity at $x^{\prime }$, then $C\left(C{H}_1\right)=I(C{H}_1,x^{\prime })\le I(C{H}_2,x^{\prime })\le C\left(C{H}_2\right)$.

Of course swapping rows, or swapping columns from the channel matrix (6) is just notational and leaves capacity unchanged. However, we end this subsection with some interesting results in information theory—some obvious, some not so obvious.

Property 1.

Removing a row from the channel matrix (6) never increases the capacity.

Proof. 

Not using a channel input cannot increase mutual information. This is equivalent to using input probability distributions which are always zero for a particular index; therefore, the capacity can never be greater since capacity is the maximum over all input distributions. □

Property 2.

A—

For any input probability, combining (by adding two columns to form one column hence reducing the channel matrix from $n\times m$ to $n\times m-1$ as illustrated below with $Q,Q^{\prime }$) two columns of a channel matrix will never increase mutual information.

B—

For input probabilities with all terms non-zero, the mutual information will stay the same iff one of the combined columns is a multiple of the other. Otherwise, the uncombined channel has a larger mutual information and hence a larger capacity. (Note, that for a 2-input channel [12] has shown that the capacity achieving distribution has both probabilities in the interval $[\frac{1}{e},1-\frac{1}{e}]$ so we can apply this property to the capacity directly.)

Proof. 

A:

$$\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)·\left(\begin{array}{cc}1& 0\\ 1& 0\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}a+b& c\\ d+e& f\\ g+h& i\end{array}\right)$$

The Data-Processing Inequality (Cascade of Channels) [3] shows that the capacity of the third channel above cannot be greater than that of the first channel. That is, processing one channel into another can never increase the information sent. The actual statement of the inequality is for mutual information. However, we use the probability that maximizes the mutual information of the first channel (which is its capacity), and therefore, it is less than or equal to the mutual information of the third channel which is less than or equal to the third channel’s capacity. This argument holds for any initial channel matrix (with adjustments to the second matrix), not just the $3\times 3$ matrix, or the columns we chose, for simplicity above.

B: Without loss of generality (WLOG), combine the first two columns of n by m channel matrix (note how the indices are reversed as compared to (6))

$$Q=\left(\begin{array}{cccc}{q}_{11}& q_{12}& \cdots & q_{1m}\\ q_{21}& q_{22}& \cdots & q_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ q_{n1}& q_{n2}& \cdots & q_{nm}\end{array}\right)\left(\mathrm{uncombined}\right)$$

to make

$$Q^{\prime }=\left(\begin{array}{ccc}{q}_{11}+q_{12}& \cdots & q_{1m}\\ q_{21}+q_{22}& \cdots & q_{2m}\\ ⋮& \ddots & ⋮\\ q_{n1}+q_{n2}& \cdots & q_{nm}\end{array}\right)\left(\mathrm{combined}\right).$$

For Q, the output symbols are $y_j$, where j goes from 1 to m. For $Q^{\prime }$, they are the same, but with $y_1$ and $y_2$ replaced by $y_1\cup y_2$. For both channels, the input symbols are $x_i$, with input probability vector p defined as

$$p_i:=p\left(x_i\right).$$

Therefore,

$$p\left(y_1\right)=\sum _{i=1}^n{p}_i{q}_{i1}$$

and

$$p\left(y_2\right)=\sum _{i=1}^n{p}_i{q}_{i2}.$$

If either of these last two relations are 0, WLOG we assume $p\left(y_1\right)=0$. This assumption means column 1 of Q must be a 0 column (since the input probabilities are positive), so it contributes 0 to the mutual information. Therefore, the mutual informations are equal, and one column is a constant multiple of the other. Now that we have dealt with this case, we can assume $y_1$ and $y_2$ are positive for the remainder of this proof. For fixed p, the mutual information of an n by m channel is

$$I=\sum _{i=1}^n\sum _{j=1}^{m}p\left(x_i\right)p\left(y_j\right|x_i)log\frac{p\left(y_j\right|x_i)}{p\left(y_j\right)}.$$

Columns 3 through m of Q and 2 through $m-1$ of $Q^{\prime }$ are the same, so their contributions to mutual information are the same. Therefore, we only need to consider columns 1 and 2 of Q and column 1 of $Q^{\prime }$. Let $\overline{I}$ be these columns’ mutual information, that is,

$$\overline{I}\left(Q\right)=\sum _{i=1}^n{p}_i{q}_{i1}log\frac{q_{i1}}{p\left(y_1\right)}+\sum _{i=1}^n{p}_i{q}_{i2}log\frac{q_{i2}}{p\left(y_2\right)},\mathrm{and}$$

$$\overline{I}\left(Q^{\prime }\right)=\sum _{i=1}^n{p}_i\left[(q_{i1}+q_{i2})log\frac{q_{i1}+q_{i2}}{p\left(y_1\right)+p\left(y_2\right)}\right],\sin \mathrm{ce}p(y_1\cup y_2)=p\left(y_1\right)+p\left(y_2\right),\mathrm{etc}.$$

Note that $\overline{I}\left(Q\right)$ can also be written as

$$\overline{I}\left(Q\right)=\sum _{i=1}^n{p}_i\left[q_{i1}log\frac{q_{i1}}{p\left(y_1\right)}+q_{i2}log\frac{q_{i2}}{p\left(y_2\right)}\right].$$

The log sum inequality [4] states that, for a series of non-negative numbers $a_k$ and $b_k$ with sums a and b, respectively, where k goes from 1 to K, then

$$\sum _{i=1}^K{a}_{i}log\frac{a_k}{b_k}\le alog\frac{a}{b},$$

with equality iff $\frac{a_k}{b_k}$ are equal for all i. By applying this inequality to the above terms in square braces, we have that $\overline{I}\left(Q^{\prime }\right)\le \overline{I}\left(Q\right)$, with equality iff $\frac{q_{1i}}{p\left(y_1\right)}=\frac{q_{2i}}{p\left(y_2\right)}$ for all i. Since $p\left(y_1\right)$ and $p\left(y_2\right)$ are nonzero and independent of i, this is true iff column 1 of Q is a constant multiple $p\left(y_1\right)/p\left(y_2\right)$ of column 2. In fact, this also shows that $p\left(y_1\right)$ is a constant multiple of $p\left(y_2\right)$, regardless of the all of the positive input probabilities. □

1.2. Back to Our Binary-Input Binary-Output DMC, the (2,2) Channel

Restating (1) and following the approach of [13]:

$$\begin{array}{cc}\hfill x=P(X=0),& \overline{x}=P(X=1)\mathrm{and}\mathrm{we}\mathrm{define}\hfill \\ \hfill y:=P(Y=0),& \mathrm{thus}\overline{y}=P(Y=1).\hfill \end{array}$$

(10)

The above expressions simplify for our DMC under investigation. Using (1) and (2), we have that the distribution of Y is

$$(y,\overline{y})=(x,\overline{x})\left(\begin{array}{cc}a& \overline{a}\\ b& \overline{b}\end{array}\right)=\left((a-b)x+b,1-\left[(a-b)x+b\right]\right)$$

We now define a differentiable function $f\left(x\right),x\in [0,1]$ by

$$f\left(x\right):=(a-b)x+b=ax+b\overline{x},$$

(11)

which gives us

$$(y,\overline{y})=(f\left(x\right),\overline{f\left(x\right)}).$$

(12)

Thus,

$$H\left(Y\right)=h\left(y\right)=h\left(f\right(x\left)\right).$$

(13)

From (5), we have that

$$\begin{array}{cc}\hfill H\left(Y\right|X)& =-\left\{x\left[aloga+\overline{a}log\overline{a}\right]+\overline{x}\left[blogb+\overline{b}log\overline{b}\right]\right\}\hfill \\ \hfill & =x·h\left(a\right)+\overline{x}·h\left(b\right).\hfill \end{array}$$

(14)

Putting the above together gives us

$$I(Y,X)=h\left(f\left(x\right)\right)-x·h\left(a\right)-\overline{x}·h\left(b\right).$$

(15)

Using (9), we have that the capacity of the (2,2) channel is

$$C_{2,2}=\underset{x}{max}I(Y,X)=\underset{x}{max}\left[h\left(f\left(x\right)\right)-x·h\left(a\right)-\overline{x}·h\left(b\right)\right].$$

(16)

So, for the (2,2) channel, the capacity calculation boils down to a (not so simple) calculus problem. Silverman [14] was the first to express the closed form result (see also [5,13] and ([Equation (5)] [7]) for derivations and alternate expressions).

$$C_{2,2}(a,b)=log\left(2^{\frac{\overline{a}·h\left(b\right)-\overline{b}·h\left(a\right)}{a-b}}+2^{\frac{b·h\left(a\right)-a·h\left(b\right)}{a-b}}\right),\mathrm{where}C(a,a):=0,$$

(17)

which is a continuous function on the unit square $[0,1]\times [0,1]$. It is trivial to show that capacity is continuous on the unit square without the main diagonal $a=b$. However, to prove continuity on the entire unit square requires some work and uses the fact that (15) is continuous in a, b, and x see ([Section 2.4] [15]).

One can easily show that (see Figure 3)

$$C_{2,2}(a,b)=C_{2,2}(b,a)=C_{2,2}(\overline{a},\overline{b}),$$

(18)

by simple algebraic substitution. Additionally, this tells us that $C_{2,2}(a,b)=C_{2,2}(\overline{b},\overline{a})$ also.

$C_{2,2}(a,b)=C_{2,2}(b,a)$ is equivalent to capacity being symmetric across the line $b=a$, and $C_{2,2}(a,b)=C_{2,2}(\overline{b},\overline{a})$ is equivalent to capacity being symmetric when across the line $b=-a+1$ (simple geometry proves this). This result is illustrated in Figure 3. Thus, capacity has a quadrant of the unit square as its principal domain (see ([Figure 1] [14])).

1.3. Power/Fidelity Constraints of $C_{2,2}$

We consider the situation where we attempt to increase the capacity by adjusting the terms a and b. Ideas like this for a Team’s interdependence, with a different measurement and no mention of information theory, were discussed in [1]. However, the values of $a,b$ are a function of the transmitting environment from $A_X$ to $A_Y$. If the agents were all-powerful, that could simply adjust a to be 1, and b to be 0 (or visa versa) to achieve a channel of maximal capacity $C_{2,2}=1$.

1.3.1. Positive Channels

Let us start by considering positive channels [6], that is $a>b$. Note if $a<b$, we have a negative channel, and if $a=b$, we have a 0-capacity channel. Of course, no matter what $C(a,b),\ge 0$. However, if we are at a point (a,b), is it better to increase a, decrease b, or some combination thereof? Implicit in this question is that we stay in the domain of positive channels (under the line $b=a$).

Definition 2.

We say that we have a power constraint P when we are at the channel given by (a,b) and the most we can adjust the channel is to $(a^{\prime },b^{\prime })$ where the standard Euclidean distance (its $l^2$ norm) between $(a,b)$ and $(a^{\prime },b^{\prime })$ is no more that P.

In terms of Information Geometry [1], our distance is obtained from the Riemannian metric

$$d{s}^2=d{a}^2+d{b}^2.$$

(19)

Of course we can generalize this to a more general metric of the form

$$d{s}^2=Ed{a}^2+Fda·db+Gd{b}^2,$$

(20)

which would put us in a non-Euclidean situation. This non-trivial situation may be necessary if a and b relate differently to various transmission characteristics.

It is shown in ([Theorem 4.9] [6]) that if we restrict ourselves to positive channels, that the capacity increases as a increases, and decreases as b increases. This result makes physical sense in terms of adding or decreasing noise. Now consider the (closed) disk of radius r about the point $(a,b)$, denoted as $D_r(a,b)$. We assume that r is small enough so that $D_r(a,b)$ is composed only of positive channels.

Example 1.

We illustrate this situation in Figure 4 by the channels that are in the disk or radius 0.15 about the point (0.6,0.2).

Theorem 1.

Given a closed disk $D_r(a,b)$ consisting of positive channels, the maximum capacity is achieved and occurs on the boundary circle $\partial D_r(a,b)$.

Proof. 

Since $C_{2,2}(a,b)$ is a continuous function on the compact set $D_r(a,b)$, it is has a maximum denoted as $C_M$. Assume that the maximum is achieved at an interior point $(a^{\prime },b^{\prime })\in D_r(a,b)$. By ([Theorem 4.9] [6]) we know that increasing $a^{\prime }$ increases capacity, which contradicts $C_M$ being achieved at the interior point $(a^{\prime },b^{\prime })$. □

We note that the above theorem still holds for non-positive channels by a simple adjustment of the proof.

Example 1 is illustrated in Figure 4 and is examined again in Figure 5 and Figure 6, where we can see the level sets of $C_{2,2}$ and the surface plot of capacity. Furthermore, numerical calculations show that the maximum of capacity for the closed disk is obtained at the boundary points $(0.68,0.07)$ and has a value of 0.32.

Of course, as the center of the disk and the radius vary, so does the relative position of the point on the circle that capacity is achieved at. What is interesting is that it is not obvious where this point should be. We will explain this further. For a positive channel, increasing a brings increased capacity, whereas decreasing b results in increased capacity. So, considering our example of the disk centered at $(0.6,0.2)$ with radius 0.15, one might think that this critical point is when b is decreased by the amount that a is increased—this being the point on the boundary circle at $2\pi -\frac{\pi }{4}=5.50$ radians, which only gives us a capacity of 0.31. However, numerical methods tell us that the actual maximum occurs are 5.25 radians with a value, as noted, of 0.32. Of course, for this example, the difference is not much, but this result is relative to the size of the disk. What is important is that the actual critical point depends on the disk’s position to the two lines $b=a$ and $b=1-a$. We do note that when the disk is centered on the line $b=1-a$, that $2\pi -\frac{\pi }{4}$ radians is the correct position for the critical point. One can also see this by examining the capacity level sets in Figure 5.

Of course, we are using an $l^2$ metric which has a metric ball of a disk. If, for example, we used an $l^1$ metric, the ball would be a square rotated by 45 degrees.

1.3.2. Power

We assume that the transmitting agent $A_X$ has adjustable power P. This power allows the transmission capabilities of $A_X$ to vary. By way of example, say that $A_X$ transmits with fidelity $a=0.6,b=0.2$. Now, $A_X$ is given an increase in its transmitting power that allows it to change $(a,b)$ to $(a^{\prime },b^{\prime })$ such that the “distance” between the two points is less than P. Consider that we use the $L_2$ Euclidean norm and set $P=0.15$. This tells us that all such points $(a^{\prime },b^{\prime })$ are in the disk of radius $0.15$ about the center $(0.6,0.2)$. We note that this is a rudimentary concept of power. Power helps a transmission when we are restricted to the bottom quarter of this disk and where a is increasing (giving more transmission fidelity) and b is decreasing (more transmission fidelity—recall that b gives us the probability of a 1 going to the opposite symbol 0). However, the conclusion is still the same point that we made and illustrated above.

1.3.3. Results and Discussion

We end this section with a brief summary. We have discussed how one agent can pass Shannon information to another and how changing the transmission characteristics can increase or decrease this information transfer. We have used capacity as our metric for information transfer. Let us now progress to multiple agents. We have also proven some information theoretic properties for the reader (Properties 1 & 2).

In the situation that we discussed in this section where there are two transmitting agents and one receiving agent, we denote the channel as $M_1$, which is given by the channel matrix (In this article, we freely identify a channel with its matrix. Furthermore, for a $2\times 2$ channel, we identify the channel as the ordered 2-tuple $(a,b)$ also.) $M_1$ described earlier (4). We denote that channel capacity as $C\left(M_1\right)$ which we have analyzed as $C_{2,2}$ in this section.

2. Two Transmitting Agents

Say we have two transmitting agents, $A_{X_1}$ and $A_{X_2}$ acting independently with respect to each other. Assume they have the same transmitting characteristics; that is, the channel matrices are the same. The receiving agent $A_Y$ gets symbols from both transmitting agents. How does this impact the information flow to $A_Y$?

In our scenario, $A_{X_1}$ and $A_{X_2}$ both sense the same environment. That is, they both wish to send a 0 or they both wish to send a 1. So, as before, the possible inputs are 0 or 1, but the outputs are of the form

$$(0,0),(0,1),(1,0),(1,1)$$

(21)

since we are assuming that the noise affects each transmitting agent independently. Keep in mind that both $A_{X_1}$ and $A_{X_2}$ are both attempting to transmit the same symbol.

The output that $A_Y$ uses is given by the random variable Y.

$$\begin{array}{cc}\hfill (0,0)& \mathrm{is}\mathrm{taken}\mathrm{to}\mathrm{be}\mathrm{the}\mathrm{symbol}Y=O_{0,0}\hfill \\ \hfill (0,1)& \mathrm{is}\mathrm{taken}\mathrm{to}\mathrm{be}\mathrm{the}\mathrm{symbol}Y=O_{0,1}\hfill \\ \hfill (1,0)& \mathrm{is}\mathrm{taken}\mathrm{to}\mathrm{be}\mathrm{the}\mathrm{symbol}Y=O_{1,0}\hfill \\ \hfill (1,1)& \mathrm{is}\mathrm{taken}\mathrm{to}\mathrm{be}\mathrm{the}\mathrm{symbol}Y=O_{1,1}.\hfill \end{array}$$

We denote $P(Y=O_{i,j})=:y_{i,j}$. Our channel matrix is $2\times 4$ and is

$$\begin{array}{ccc}\hfill M_2& =& \left(\begin{array}{cccc}P(Y=O_{0,0}|X=0)& P(Y=O_{0,1}|X=0)& P(Y=O_{1,0}|X=0)& P(Y=O_{1,1}|X=0)\\ P(Y=O_{0,0}|X=1)& P(Y=O_{0,1}|X=1)& P(Y=O_{1,0}|X=1)& P(Y=O_{1,1}|X=1)\end{array}\right)\hfill \\ & =& \left(\begin{array}{cccc}{a}^2& a\overline{a}& \overline{a}a& {\overline{a}}^2\\ b^2& b\overline{b}& \overline{b}b& {\overline{b}}^2\end{array}\right).\hfill \end{array}$$

We note that the second and third columns of the above channel matrix are identical. This has implications for the mutual information and, of course, the capacity of the channel.

Let us look at this in more generality. Say we have two channel matrices

$$M^3=\left(\begin{array}{ccc}\alpha & 2ϵ& \delta \\ \beta & 2\gamma & \varphi \end{array}\right)\mathrm{and}{M}^4=\left(\begin{array}{cccc}\alpha & ϵ& ϵ& \delta \\ \beta & \gamma & \gamma & \varphi \end{array}\right).$$

Both channels have the same input random variable X as above. The output random variables are $Y^3$ and $Y^4$, respectively.

Let us consider the $M^3$ channel first. $Y^3$ has probability values $y_i:=P(Y^3=i)$ as follows

$$(y_1,y_2,y_3)=(\alpha x+\beta \overline{x},2ϵx+2\gamma \overline{x},\delta x+\varphi \overline{x}).\mathrm{So},H\left(Y^3\right)$$

$$=-\left[(\alpha x+\beta \overline{x})log(\alpha x+\beta \overline{x})+(2ϵx+2\gamma \overline{x})log(2ϵx+2\gamma \overline{x})+(\delta x+\varphi \overline{x})log(\delta x+\varphi \overline{x})\right],$$

$$\begin{array}{cc}\hfill H\left(Y^3\right|X)& =-x\left[\alpha log\left(\alpha \right)+2ϵlog\left(2ϵ\right)+\delta log\left(\delta \right)\right]\hfill \\ & -\overline{x}\left[\beta log\left(\beta \right)+2\gamma log\left(2\gamma \right)+\varphi log\left(\varphi \right)\right].\hfill \end{array}$$

(22)

The mutual information is $I(Y,X)=H\left(Y\right)-H\left(Y\right|X)$. We expand the mutual information into the sum of two functions. The first function is from the first and last columns, and the second function is from the middle column. That is

$$I(Y^3,X)=F_1^3(\alpha ,\beta ,\delta ,\varphi ,x)+F_2^3(ϵ,\gamma ,x),\mathrm{where}$$

$$\begin{array}{ccc}\hfill F_2^3& =& -2ϵxlog(2ϵx+2\gamma \overline{x})-2\gamma \overline{x}log(2ϵx+2\gamma \overline{x})+2ϵxlog\left(2ϵ\right)+2\gamma \overline{x}log\left(2\gamma \right)\hfill \\ & =& 2ϵxlog\left(\frac{2ϵ}{2ϵx+2\gamma \overline{x}}\right)+2\gamma \overline{x}log\left(\frac{2\gamma }{2ϵx+2\gamma \overline{x}}\right)\hfill \\ & =& 2ϵxlog\left(\frac{ϵ}{ϵx+\gamma \overline{x}}\right)+2\gamma \overline{x}log\left(\frac{\gamma }{ϵx+\gamma \overline{x}}\right).\hfill \end{array}$$

Now let us consider the $M^4$ channel. As above

$$(y_1,y_2,y_3,y_4)=(\alpha x+\beta \overline{x},ϵx+\gamma \overline{x},ϵx+\gamma \overline{x},\delta x+\varphi \overline{x}).$$

$$\begin{array}{cc}\hfill H\left(Y^4\right)& =-[(\alpha x+\beta \overline{x})log(\alpha x+\beta \overline{x})+(ϵx+\gamma \overline{x})log(ϵx+\gamma \overline{x})\hfill \end{array}$$

$$\begin{array}{cc}\hfill & +(ϵx+\gamma \overline{x})log(ϵx+\gamma \overline{x})+(\delta x+\varphi \overline{x})log(\delta x+\varphi \overline{x})]\hfill \\ \hfill & =-[(\alpha x+\beta \overline{x})log(\alpha x+\beta \overline{x})+2(ϵx+\gamma \overline{x})log(ϵx+\gamma \overline{x})\hfill \end{array}$$

(23)

$$\begin{array}{cc}\hfill & +(\delta x+\varphi \overline{x})log(\delta x+\varphi \overline{x})].\hfill \end{array}$$

(24)

$$\begin{array}{cc}\hfill H\left(Y^4\right|X)& =-x\left[\alpha log\left(\alpha \right)+ϵlog\left(ϵ\right)+ϵlog\left(ϵ\right)+\delta log\left(\delta \right)\right]\hfill \end{array}$$

$$\begin{array}{cc}& -\overline{x}\left[\beta log\left(\beta \right)+\gamma log\left(\gamma \right)+\gamma log\left(\gamma \right)+\varphi log\left(\varphi \right)\right]\hfill \\ \hfill & =-x\left[\alpha log\left(\alpha \right)+2ϵlog\left(ϵ\right)+\delta log\left(\delta \right)\right]\hfill \end{array}$$

(25)

$$\begin{array}{cc}& -\overline{x}\left[\beta log\left(\beta \right)+2\gamma log\left(\gamma \right)+\varphi log\left(\varphi \right)\right].\hfill \end{array}$$

(26)

As above we expressthe mutual information as

$$I(Y^3,X)=F_1^3(\alpha ,\beta ,\delta ,\varphi ,x)+F_2^3(ϵ,\gamma ,x)$$

and we have that

$$\begin{array}{ccc}\hfill F_2^4& =& -2ϵxlog(ϵx+\gamma \overline{x})-2\gamma \overline{x}log(ϵx+\gamma \overline{x})+2ϵxlog\left(ϵ\right)+2\gamma \overline{x}log\left(\gamma \right)\hfill \\ & =& 2ϵxlog\left(\frac{ϵ}{ϵx+\gamma \overline{x}}\right)+2\gamma \overline{x}log\left(\frac{\gamma }{ϵx+\gamma \overline{x}}\right)=F_2^3.\hfill \end{array}$$

A quick inspection tells us that $F_1^4=F_1^3$; thus, the mutual information of both channels is the same. This result is not surprising because if we combine output symbols where the channel matrix has identical rows, we lose nothing as far as the output information is concerned—there is no extra value in looking at the output symbols separately. This makes sense, and is also what our mathematics have shown.

Let us keep in mind that we wish to find $C\left(M_2\right)$, the capacity of the Shannon channel when there are two transmitting agents. (To keep our notation consistent, $C(a,b)$ is the capacity given by the corresponding $2\times 2$ channel matrix as in (4), whereas $C(\ast )$ is the capacity of the channel given by *).

Theorem 2.

$C\left(M_2\right)\ge C\left(M_1\right)$.

Proof. 

$M_2$ has four output symbols which are in essence 2-vectors. We ignore the second component of the vector. Therefore, we collapse the first and third symbol to a, and the second and fourth to $\overline{a}$. This results in $M_1$, and since using more output symbols never lowers capacity, by Property 2 (also, a code that works for $M_1$ works for $M_2$ as well by collapsing the symbols), we are done. (Later in the paper we do better than this result with Corollary 1 to Theorem 6.) □

We now form another channel related to what we discussed above. Say now that the receiving agent receives the symbols without any order. Therefore, instead of a 2-vector, the output is one of the three multisets $[0,0],[1,0],[1,1]$ with

$$P(Y=[0,0])=a^2,P(Y=[1,0])=2\overline{a}a,P(Y=[1,1])={\overline{a}}^2.$$

We call this channel $M_{2-}$, and its channel matrix is

$$M_{2-}=\left(\begin{array}{ccc}{a}^2& 2\overline{a}a& {\overline{a}}^2\\ b^2& 2\overline{b}b& {\overline{b}}^2\end{array}\right).$$

From what we discussed above with $M^4$ and $M^3$, we see that

Theorem 3.

$$C\left(M_{2-}\right)=C\left(M_2\right).$$

Let us examine the bounds in Theorem 1 above. We will see that, not surprisingly except for special cases, $C\left(M_2\right)>C\left(M_1\right)$. Figure 7 is a plot of $C\left(M_2\right)-C\left(M_1\right)$ as a function of $(a,b)$.

From Figure 7, we see that except for the line $b=a$ (where both channels $M_1$ and $M_2$ have 0 capacity), and at $(a,b)=(1,0)$ or $(a,b)=(0,1)$ (where both channels have capacity 1), that $C\left(M_2\right)>C\left(M_1\right)$. We note that for $M_2$ and the other higher dimensional channels that we will discuss, there is to our knowledge no closed form as there is for $M_1$. Therefore, for our calculations of capacity, we rely upon numerical results from the Blahut-Arimoto capacity algorithm [16,17].

Results and Discussion

In this section, we have laid the groundwork for n transmitting agents. We derived some capacity results. We concentrated on the effects of going from 1 to 2 transmitting agents. What happens as we go to three or more transmitting agents?

3. Multiple Transmitting Agents

We have the canonical representation for the channel of n transmitting agents, and we denote this canonical channel matrix as $M_{\underline{n}}$, which is formed by taking the output of channel $M_{\underline{n-1}}$ (Note, due to the simplicity of the construction for “small” channels, we have that $M_{\underline{1}}=M_1,M_{\underline{2}}=M_2$.) and adding a 0 or a 1 to it. For $M_{\underline{3}}$ this results in

$$M_{\underline{3}}=\left(\begin{array}{cccccccc}{a}^3& a^2\overline{a}& a^2\overline{a}& a{\overline{a}}^2& a^2\overline{a}& a{\overline{a}}^2& a{\overline{a}}^2& {\overline{a}}^3\\ b^3& b^2\overline{b}& b^2\overline{b}& b{\overline{b}}^2& b^2\overline{b}& b{\overline{b}}^2& b{\overline{b}}^2& {\overline{b}}^3\end{array}\right).$$

This comes from taking the output for two agents as given in canonical form by (21) and extending it to

$$(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1).$$

Theorem 4.

Rearranging outputs/columns of a channel matrix does not affect capacity.

Proof. 

By looking at the expression for mutual information, we see that changing the order of arithmetic operations leaves it unchanged. This result follows, since capacity is the maximum of mutual information. □

Therefore, we can permute the columns of $M_{\underline{n}}$ and obtain a new matrix $M_n$, which has the same capacity, that is $C\left(M_n\right)=C\left(M_{\underline{n}}\right)$, and is given below.

$$M_n=\left(\begin{array}{ccccccccc}{a}^n& a^{n-1}\overline{a}& \dots & a^{n-1}\overline{a}& a^{n-2}{\overline{a}}^2& \dots & a^{n-1}\overline{a}& \dots & {\overline{a}}^n\\ b^n& b^{n-1}\overline{b}& \dots & b^{n-1}\overline{b}& b^{n-2}{\overline{b}}^2& \dots & b^{n-1}\overline{b}& \dots & {\overline{b}}^n\end{array}\right).$$

(27)

Look at the above theorem in terms of the columns of $M_n$. Let us use $M_3$ as an example.

$$M_3=\left(\begin{array}{cccccccc}{a}^3& a^2\overline{a}& a^2\overline{a}& a^2\overline{a}& a{\overline{a}}^2& a{\overline{a}}^2& a{\overline{a}}^2& a^3\\ b^3& b^2\overline{b}& b^2\overline{a}& b^2\overline{b}& b{\overline{b}}^2& b{\overline{b}}^2& b{\overline{b}}^2& b^3\end{array}\right).$$

(28)

Collapsing the output in this situation is equivalent to interchanging the 4th and 5th columns (which does not change capacity) and forming the matrix $M_{3c}$.

$$M_{3c}=\left(\begin{array}{cccccccc}{a}^3& a^2\overline{a}& a^2\overline{a}& a{\overline{a}}^2& a^2\overline{a}& a{\overline{a}}^2& a{\overline{a}}^2& a^3\\ b^3& b^2\overline{b}& b^2\overline{a}& b{\overline{b}}^2& b^2\overline{b}& b{\overline{b}}^2& b{\overline{b}}^2& b^3\end{array}\right).$$

(29)

As above when we looked at $M^3$ and $M_4$, we see that we may form the channel where we identify output symbols with the same conditional probabilities for both inputs. This give us the channel $M_n-$, where

$$M_{n-}=\left(\begin{array}{cccccc}{a}^n& n{a}^{n-1}\overline{a}& \left(\genfrac{}{}{0pt}{}{n}{2}\right)a^{n-2}{\overline{a}}^2& \dots & na{\overline{a}}^{n-1}& {\overline{a}}^n\\ b^n& n{b}^{n-1}\overline{b}& \left(\genfrac{}{}{0pt}{}{n}{2}\right)b^{n-2}{\overline{b}}^2& \dots & nb{\overline{b}}^{n-1}& {\overline{b}}^n\end{array}\right).$$

(30)

Theorem 5.

$C\left(M_n\right)=C\left(M_{n-}\right)$

Proof. 

As above for $M_2$ in Theorem 3, or we can just use Property 2 repeatedly. □

The reason we introduce $M_{n-}$ is that it is a cleaner way to express the channel, and the calculations are simpler than that of $M_n$. For example, $M_8$ is a $2\times 256$ matrix, whereas $M_{8-}$ is a $2\times 9$ matrix. This obviously makes the coding issues easier. Now we examine Figure 8, which is the difference between $C\left(M_8\right)$ and $C\left(M_1\right)$.

When we compare Figure 8 to Figure 7, we easily see that $C\left(M_n\right)$ grows, except for the endpoints and the line $b=a$ (which stay at 0) as n grows.

Nota Bene We now look at the prior illustrative results in terms of a more general encompassing theory. We included much of Section 2 so that the reader who is not familiar with some of the “tricks” will have a feel for why the more general results hold.

Theorem 6.

$C\left(M_{n+1}\right)\ge C\left(M_n\right)$ for any positive integer n.

Proof.

(The proof is the same as for the above when $n=1$.) $M_n$ can be obtained from $M_{n+1}$ by combining certain columns together; the result follows from Property 2. □

Corollary 1.

$C\left(M_{n+1}\right)>C\left(M_n\right)$, except for $(1,0)$ and $(0,1)$ where they both have capacity 1, and the line $b=a$ where they both have capacity 0.

Proof. 

We show the proof in three steps.

• If $a=b$, $C\left(M_n\right)=C\left(M_{n+1}\right)=0$ since the rows are identical. In this case, it is trivial to show that $H\left(Y\right)=H\left(Y\right|X)$ (the output has no idea what the channel input was). One can see this by the fact that $x·a^q{\overline{a}}^{n-q}+\overline{x}·a^q{\overline{a}}^{n-q}=a^q{\overline{a}}^{n-q}$. In short, the capacities are equal.
• If $(a,b)=(1,0)$ or $(a,b)=(0,1)$, both $M_n$ and $M_{n+1}$ are both the $2\times 2$ identity matrix with zero columns added in; hence, $C\left(M_n\right)=C\left(M_{n-1}\right)=1$. In short, the channel capacities are equal.
• Now, excluding the special cases where $a=b$, $(a,b)=(1,0)$, or $(a,b)=(0,1)$, by Property 2, we only have to show that here are two combined columns that are not multiples of each other.

By excluding the special cases, we cannot use the endpoints of the unit square; therefore, a or b must be in $(0,1)$. WLOG, we assume that $0<a<1$.

Consider a generic column of $M_n$; it is of the form $c=\left(\begin{array}{c}{a}^e{\overline{a}}^{n-e}\\ b^e{\overline{b}}^{n-e}\end{array}\right),e\in \{0,\dots ,n\}$. By construction, $M_{n+1}$ has two columns, $c_1=\left(\begin{array}{c}a·a^e{\overline{a}}^{n-e}\\ b·b^e{\overline{b}}^{n-e}\end{array}\right)$ and $c_2=\left(\begin{array}{c}\overline{a}·a^e{\overline{a}}^{n-e}\\ \overline{b}·b^e{\overline{b}}^{n-e}\end{array}\right),$ that when combined result in column c. If $c_1$ is not a constant multiple of $c_2$, we will have shown that $C\left(M_{n+a}\right)>C\left(M_n\right)$. Assume the opposite—that is, $c_1=k·c_2$; since neither a or $\overline{a}$ is 0 we have that $a=k\overline{a}$. Then $a=k\overline{a}$ is equivalent to $a=\frac{k}{k+1},k\ne 0$. We now have three cases for b.

• $b=0$. In this case, $\overline{b}=1$ and we only look at the last column of $M_n$, so we let $c=\left(\begin{array}{c}{\overline{a}}^n\\ {\overline{b}}^n\end{array}\right)=\left(\begin{array}{c}{\overline{a}}^n\\ 1\end{array}\right).$ Since we are assuming that $c_1=k·c_2$, we have that
  $0=0·1=b·1=k·\overline{b}·1=k$, which is impossible.
• $b=1$. Using the same argument as above, just replace the last column of $M_n$ with the first. So again, it is impossible that the columns are multiples.
• $0<b<1$. As above for a, we also have that $b=\frac{k}{k+1}$. This tells us that $a=b$ which has been ruled out.

Thus, we have shown the existence of two columns of $M_{n+1}$ that are not multiples of each other and combine them into a column of $M_n$. □

Theorem 7.

${lim}_{n\to \infty }C\left(M_n\right)=1$, except for when $b=a$, and in that case, the channel capacity is 0.

Proof. 

WLOG, we assume $a>b$. We can do this because of the constraint $a\ne b$ and the fact that the rows of a channel matrix can be interchanged without affecting its capacity. Take a positive $\epsilon <<\frac{a-b}{2}$ be fixed. For a large enough N, we can always find a rational number $m\left(n\right)$ for any $n>N$ such that $\overline{a}+\epsilon <m<\overline{b}-\epsilon <1$ and $nm\in \mathbb{Z}$. (The $\epsilon$ padding prevents m from converging to $\overline{a}$ or $\overline{b}$). This result is guaranteed to exist for sufficiently large N.

Given $0\le b<a\le 1$, let $x=\overline{a}+\epsilon ,y=\overline{b}-\epsilon$, giving us $0\le x<y\le 1$. Certainly there exists a positive integer N such that $1/N<y-x$. Therefore, for any integer $n\ge N$, we have that $1/n<y-x$. Consider $(x,y)$ as a sub-interval of $[0,1]$. For any $n\ge N$, consider the largest integer W such that $W(1/n)\le x$. Look at $(W+1)(1/n)$; by the definition of W, this must be greater than x. However, since $1/n<y-x$, we have that $(W+1)(1/n)<y$. We let $m=(W+1)(1/n)$. Keep in mind two characteristics of m as a function of n:

• Since W is an integer, $mn\in \mathbb{Z}$, and,
• $mn<n$, since $m<1$.

Let $M_n^{\prime }$ be the channel matrix $M_{n-}$, but modified as follows: all outputs $y_k$ for $k\le mn$ are combined into $y_0^{\prime }$, and all of the other outputs are combined into $y_1^{\prime }$. The channel matrix then looks like this:

$$M_n^{\prime }=\left(\begin{array}{cc}P\left(y_0^{\prime }\right|x_0)& P\left(y_1^{\prime }\right|x_0)\\ P\left(y_0^{\prime }\right|x_1)& P\left(y_1^{\prime }\right|x_1)\end{array}\right),$$

where

$$(Y=y_0^{\prime })=(Y=y_0)\cup (Y=y_1)\cup \dots \cup (Y=y_{mn})⊊(Y=y_o)\cup \dots \cup (Y=y_n)\mathrm{and}$$

$$P\left(y_0^{\prime }\right|x_0)=\sum _{i=0}^{mn}P\left(y_i\right|x_0),\mathrm{with}P\left(y_i\right|x_0)=\left(\genfrac{}{}{0pt}{}{n}{i}\right)a^{n-i}{\overline{a}}^i.$$

(Keep in mind that we are dealing with the binomial random variable $S_n$, where i is the number of successes in n Bernoulli trials, with the probability of success $\overline{a}$, $P(S_n=i)=\left(\genfrac{}{}{0pt}{}{n}{i}\right)a^{n-i}{\overline{a}}^i$).

$$\therefore P\left(y_0^{\prime }\right|x_0)=\sum _{i=0}^{mn}\left(\genfrac{}{}{0pt}{}{n}{i}\right)a^{n-i}{\overline{a}}^i.$$

If we let $\Phi \left(x\right)$ be the cumulative standard normal distribution function, the De-Moivre Laplace limit theorem [18] states that (when we take $c,d$ as integers)

$$\begin{array}{c}\hfill P\left(c<\frac{S_n-n\overline{a}}{\sqrt{na\overline{a}}}<d\right)\to \Phi \left(d\right)-\Phi \left(c\right)\mathrm{as}n\to \infty ;\mathrm{thus},\\ \hfill P\left(\frac{c-\overline{a}}{\sqrt{na\overline{a}}}<\frac{S_n-n\overline{a}}{\sqrt{na\overline{a}}}<\frac{d-\overline{a}}{\sqrt{na\overline{a}}}\right)\to \Phi \left(\frac{d-\overline{a}}{\sqrt{na\overline{a}}}\right)-\Phi \left(\frac{c-\overline{a}}{\sqrt{na\overline{a}}}\right)\mathrm{as}n\to \infty ,\mathrm{and}\\ \hfill P\left(c\le S_n\le d\right)\to \Phi \left(\frac{d-\overline{a}}{\sqrt{na\overline{a}}}\right)-\Phi \left(\frac{c-\overline{a}}{\sqrt{na\overline{a}}}\right)\mathrm{as}n\to \infty .\end{array}$$

This step leaves us with

$$\sum _{i=c}^d\left(\genfrac{}{}{0pt}{}{n}{i}\right)a^{n-i}{\overline{a}}^i\to \Phi \left(\frac{d-n\overline{a}}{\sqrt{na\overline{a}}}\right)-\Phi \left(\frac{c-n\overline{a}}{\sqrt{na\overline{a}}}\right)\mathrm{as}n\to \infty .$$

(31)

Thus, the De-Moivre Laplace limit theorem gives us (with $c=0,d=mn$):

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim}P\left(y_0^{\prime }\right|x_0)& =\underset{n\to \infty }{lim}\left[\Phi \left(\frac{mn-n\overline{a}}{\sqrt{na\overline{a}}}\right)-\Phi \left(\frac{-n\overline{a}}{\sqrt{na\overline{a}}}\right)\right]\hfill \\ \hfill & =\underset{n\to \infty }{lim}\Phi \left(\sqrt{n}\frac{m-\overline{a}}{\sqrt{a\overline{a}}}\right)-\underset{n\to \infty }{lim}\Phi \left(\sqrt{n}\frac{-\overline{a}}{\sqrt{a\overline{a}}}\right).\hfill \end{array}$$

Since a and $\overline{a}$ are positive, then $-\frac{\overline{a}}{\sqrt{a\overline{a}}}$ is negative, giving

$$\underset{n\to \infty }{lim}\sqrt{n}\frac{-\overline{a}}{\sqrt{a\overline{a}}}=-\infty ,\mathrm{and}$$

$$\underset{n\to \infty }{lim}\Phi \left(\sqrt{n}\frac{-\overline{a}}{\sqrt{a\overline{a}}}\right)=0.$$

If $m<\overline{a}$, then $\frac{m-\overline{a}}{\sqrt{a\overline{a}}}$ is negative. However, if $m>\overline{a}$, it is positive, giving (Even though m changes as n changes, the value of $\sqrt{n}\frac{m-\overline{a}}{\sqrt{a\overline{a}}}$ remains greater than or equal to $\sqrt{n}\frac{\epsilon }{\sqrt{a\overline{a}}}$ for $m>\overline{a}+\epsilon$. Since $\sqrt{n}\frac{\epsilon }{\sqrt{a\overline{a}}}$ approaches ∞, so does $\sqrt{n}\frac{m-\overline{a}}{\sqrt{a\overline{a}}}$. The same logic can also be used for the $m<\overline{a}-\epsilon$ case.)

$$\underset{n\to \infty }{lim}\sqrt{n}\frac{m-\overline{a}}{\sqrt{a\overline{a}}}=\left\{\begin{array}{cc}-\infty \hfill & \mathrm{if}m<\overline{a}-\epsilon \hfill \\ \infty \hfill & \mathrm{if}m>\overline{a}+\epsilon ;\mathrm{and}\hfill \end{array}\right.$$

$$\underset{n\to \infty }{lim}\Phi \left(\sqrt{n}\frac{m-\overline{a}}{\sqrt{a\overline{a}}}\right)=\left\{\begin{array}{cc}0\hfill & \mathrm{if}m<\overline{a}-\epsilon \hfill \\ 1\hfill & \mathrm{if}m>\overline{a}+\epsilon \hfill \end{array}\right.$$

$$\therefore \underset{n\to \infty }{lim}P\left(y_0^{\prime }\right|x_0)=1-0=1.$$

Thus, we have that

$$\underset{n\to \infty }{lim}P\left(y_1^{\prime }\right|x_0)=0.$$

$P\left(y_0^{\prime }\right|x_1)$ beahves the same, but with a replaced by b. Since $\overline{a}+\epsilon <m<\overline{b}-\epsilon$, then the ${lim}_{n\to \infty }P\left(y_0^{\prime }\right|x_0)=1$ and ${lim}_{n\to \infty }P\left(y_0^{\prime }\right|x_1)=0$; thus,

$$\underset{n\to \infty }{lim}{M}_n^{\prime }=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right).$$

which has a channel capacity of 1. Since $M_n^{\prime }$ was formed by combining the outputs of $M_n$, then $C\left(M_n^{\prime }\right)\le C\left(M_n\right)\le 1$. Therefore, by the squeeze theorem, ${lim}_{n\to \infty }C\left(M_n\right)=1$. □

Results and Discussion

The theorems presented in this section shows what happens as the number of transmitters grows. The ultimate result of this section was Theorem 7, which used a rather non-trivial application of the Central Limit Theorem. At this point, the seemingly obvious but difficult result that we proved, i.e., that as the number of transmitting agents grows, so does the reliability of the channel in terms of its capacity. This result, of course, is in line with the similar result that if we have a code that consisted of repeating a symbol many times the error rate is small (the transmission rate may be low, but this does not apply to our agent examples).

4. Non-Identical Transmitting Agents

In a shift, say we start with only two transmitting agents, but their noise characteristics are different. Of course, keep in mind that in this situation, we have assumed that there is a master transmitter using the X agent to communicate with Y. The master transmitter picks the input symbols and the transmitting agents do their best to communicate by forming one encompassing Shannon channel. We have shown above that, if all of the agents share the same assumption for $(a,b)$, the channel capacity increases as the number of agents increase. However, what happens if the $(a,b)$ are different for the various agents? Are we better off only using a subset of agents, or is it still best to use as many agents as possible? We partially answer those questions below.

Let $M_1^1$ be the channel matrix for agent 1, and $M_1^2$ be the channel matrix for agent 2.

$$M_1^1=\left(\begin{array}{cc}a& \overline{a}\\ b& \overline{b}\end{array}\right),$$

$$M_1^2=\left(\begin{array}{cc}c& \overline{c}\\ d& \overline{d}\end{array}\right).$$

The output is such that the receiving agent uses the ordering of agent 1 first, then agent 2. If the agents wish to send a signal of 0, the possible outputs, expressed via their probabilities, are

$$\begin{array}{cc}\hfill P(0,0)& =ac\\ \hfill P(0,1)& =a\overline{c}\\ \hfill P(1,0)& =\overline{a}c\\ \hfill P(1,1)& =\overline{a}\overline{c}\end{array}$$

If the agents wish to send a signal of 1 instead, we have

$$\begin{array}{cc}\hfill P(0,0)& =bd\\ \hfill P(0,1)& =b\overline{d}\\ \hfill P(1,0)& =\overline{b}d\\ \hfill P(1,1)& =\overline{b}\overline{d}.\end{array}$$

This gives us a combined channel matrix for both agents who are transmitting as $M_2^{1,2}$, where

$$M_2^{1,2}=\left(\begin{array}{cccc}ac& a\overline{c}& \overline{a}c& \overline{a}\overline{c}\\ bd& b\overline{d}& \overline{b}d& \overline{b}\overline{d}\end{array}\right).$$

(32)

We use our own notation to express the above channel as the tensor product,

$$(a,b)\otimes (c,d).$$

We know, by Property 2, that collapsing output symbols does not increase capacity. However, if we collapse $y_1$ and $y_2$ into $y_{1^{\prime }}$ and $y_3$ and $y_4$ into $y_{2^{\prime }}$, we have a channel matrix of $M_{2^{\prime }}^{1,2}$:

$$M_{2^{\prime }}^{1,2}=\left(\begin{array}{cc}ac+a\overline{c}& \overline{a}c+\overline{a}\overline{c}\\ bd+b\overline{d}& \overline{b}d+\overline{b}\overline{d}\end{array}\right)=\left(\begin{array}{cc}a& \overline{a}\\ b& \overline{b}\end{array}\right).$$

Thus, $C\left(M_2^{1,2}\right)\ge C\left(M_{2^{\prime }}^{1,2}\right)=C\left(M_1^1\right)$.

Now let us combine the first and third outputs of $M_2^{1,2}$ into $y_{1^{\prime \prime }}$ and the second and fourth outputs into $y_{2^{\prime \prime }}$. This gives us a channel matrix $M_{2^{\prime \prime }}^{1,2}$.

$$M_{2^{\prime \prime }}^{1,2}=\left(\begin{array}{cc}ac+\overline{a}c& a\overline{c}+\overline{a}\overline{c}\\ bd+\overline{b}d& b\overline{d}+\overline{b}\overline{d}\end{array}\right)=\left(\begin{array}{cc}c& \overline{c}\\ d& \overline{d}\end{array}\right).$$

Thus, $C\left(M_2^{1,2}\right)\ge C\left(M_{2^{\prime \prime }}^{1,2}\right)=C\left(M_1^2\right)$. This result leads us to the next theorem:

Theorem 8.

As the number of agents increase, no matter if they have different channel noises, the total channel capacity is non-decreasing.

Proof. 

In the above discussion we have show that

$$\begin{array}{c}\hfill C\left(M_2^{1,2}\right)\ge C\left(M_{2^{\prime }}^{1,2}\right)=C\left(M_1^1\right)\\ \hfill C\left(M_2^{1,2}\right)\ge C\left(M_{2^{\prime \prime }}^{1,2}\right)=C\left(M_1^2\right).\end{array}$$

Therefore, by repeating the same argument we see that as we add extra agents the capacity can never decrease. □

In fact, as before when the agents had identical characteristics, the channel capacity, except for special cases (dependent columns, a capacity 0 or 1, etc.), is greater than that for separate agents. One can see this by examining the channel matrix—if you unpack the outputs and find that the statistics are different, extra information is learned. Let us now look at the special case of combining a channel with a 0-channel.

Theorem 9.

For any zero channel given by $(e,e),e\in [0,1]$, we find that

$$C\left((a,b)\otimes (e,e)\right)=C(a,b).$$

Proof. 

If we can show that the mutual information of $(a,b)\otimes (e,e)$ is given by (15), we are done. The channel matrix for this situation is

$$\left(\begin{array}{cccc}ae& a\overline{e}& \overline{a}e& \overline{a}\overline{e}\\ be& b\overline{e}& \overline{b}e& \overline{b}\overline{e}\end{array}\right).$$

Let $u:=ax+b\overline{x}$, and we find that $\overline{u}=\overline{a}x+\overline{b}\overline{x}$. Further,

$$\begin{array}{ccc}\hfill Y=(y_1,y_2,y_3,y_4)& =& (aex+be\overline{x},a\overline{e}x+b\overline{e}\overline{x},\overline{a}ex+\overline{b}e\overline{x},\overline{a}\overline{e}x+\overline{b}\overline{e}\overline{x})\hfill \\ & =& (ue,u\overline{e},\overline{u}e,\overline{u}\overline{e}),\hfill \end{array}$$

$$\begin{array}{ccc}\hfill H\left(Y\right)& =& -\left[uelog\left(ue\right)+u\overline{e}log\left(u\overline{e}\right)+\overline{u}elog\left(\overline{u}e\right)+\overline{u}\overline{e}log\left(\overline{u}\overline{e}\right)\right]\hfill \\ & =& -\left[ue(log\left(u\right)+log\left(e\right))+u\overline{e}(log\left(u\right)+log\left(\overline{e}\right))\right.\hfill \\ & & \left.+\overline{u}e(log\left(\overline{u}\right)+log\left(e\right))+\overline{u}\overline{e}(log\left(\overline{u}\right)+log\left(\overline{e}\right))\right]\hfill \\ & =& -\left[ulog\left(u\right)+\overline{u}log\overline{u}+elog\left(e\right)+\overline{e}log\left(\overline{e}\right)\right]\hfill \\ & =& h\left(u\right)+h\left(e\right),\mathrm{and}\hfill \end{array}$$

$$\begin{array}{ccc}\hfill H\left(Y\right|X)& =& -x\left[aelog\left(ae\right)+a\overline{e}log\left(a\overline{e}\right)+\overline{a}elog\left(\overline{a}e\right)+\overline{a}\overline{e}log\left(\overline{a}\overline{e}\right)\right]\hfill \\ & & -\overline{x}\left[belog\left(be\right)+b\overline{e}log\left(b\overline{e}\right)+\overline{b}elog\left(\overline{b}e\right)+\overline{b}\overline{e}log\left(\overline{b}\overline{e}\right)\right].\hfill \end{array}$$

Now again using the log of a product as the sum of the logs, then grouping like log terms, this results in

$$H\left(Y\right|X)=x\left[h\left(a\right)+h\left(e\right)\right]+\overline{x}\left[h\left(b\right)+h\left(e\right)\right]=x·h\left(a\right)+\overline{x}·\left(b\right)+h\left(e\right),$$

and we see that $H\left(Y\right)-H\left(Y\right|X)=h(ax+b\overline{x})-x·h\left(a\right)-\overline{x}·h\left(b\right).$ □

Results and Discussion

In this section, we showed what happens when two transmitting agents with different noise characteristics are used. Our important result was that as the number of agents increase, no matter if they have different channel noises, the total channel capacity is non-decreasing. As with many of our results it relied upon the algebra of mutual information giving common sense answers. However, without proofs we just have intuition to rely upon.

5. Resource Allocation

We now concern ourselves with the physical limitations of the receiving agent. We assume that the receiving agent has a limited resource $\mathcal{R}$ that it can use to receive messages. To the extent possible, the receiving resource, $\mathcal{R}$, may be measured in terms of various antennas or various allocations of frequencies, etc. It is not our goal in this article to discuss the engineering of the receiving agent in general. Rather, we accept it as a given.

Upon completion of the mathematics in this section, the results do not seem surprising. That is good! It shows that our intuition is correct and it lays a foundation for dealing with many agents and non-linear allocation schemes (where we lose elements of intuition). Furthermore, aside from linearity, we based our allocation scheme on a Euclidean metric; it is not at all clear if an information geometric-style Riemannian metric be used instead. That is beyond the scope of the article.

Let us take the simplest case where there are two transmitting agent $A_{X_1}$ and $A_{X_2}$. As before, $A_{X_i}$ has channel matrix $M_i$. We model noise affecting each channel in a linear manner. Suppose that an agent $A_X$ is given, as before, by its channel matrix

$$M_1=\left(\begin{array}{cc}a& \overline{a}\\ b& \overline{b}\end{array}\right).$$

How does noise, which results from the receiving agent not allocating enough of its resources to $A_X$, change this channel matrix? The channel $(a,b)$ is a point in $[0,1]\times [0,1]$. Consider the shortest path from $(a,b)$ to the main diagonal (which consists of zero-capacity channels). View $[0,1]\times [0,1]$ as sitting ${\mathbb{R}}^2$ and consider the straight line $y=-x+(a+b)$. This line is orthogonal to the straight diagonal line of zero-capacity channels, goes through the point $(a,b)$, and intersects the line for the zero-capacity channels at $(\frac{a+b}{2},\frac{a+b}{2})$. The line segment of interest is given parametrically for $t\in [0,1]$ as

$$(1-t)\left(a,b\right)+t\left(\frac{a+b}{2},\frac{a+b}{2}\right).$$

We model noise as moving on this new line segment from the point $(a,b)$ to the point $(\frac{a+b}{2},\frac{a+b}{2})$. No noise corresponds to $t=0$, total noise to $t=1$; that is, we use t as a measure of the noise normalized in a linear manner between 0 and 1.

EXAMPLE: Let $(a,b)=(0.8,0.4)$. If $t=0$, the channel is given as $(0.8,0.4)$ and the capacity is 0.12. If $t=1$, the channel is given as $(0.6,0.6)$ and the capacity is 0. Let $t=0.9$, then the channel is given by $0.1(0.8,0.4)+0.9(0.6,0.6)=(0.08,0.04)+(0.54,0.54)=(0.62,0.58)$, which has a capacity of 0.001.

Now, let $t=0.1$, then the channel is given by $0.9(0.8,0.4)+0.1(0.6,0.6)=(0.72,0.36)+(0.06,0.06)=(0.78,0.42)$, which has a capacity of .10. Note that, unsurprisingly, the cleaner channel has $C(0.8,0.4)=0.1246>C(0.78,0.42)$.

What we have been discussing motivates the following our modeling definition.

Definition 3.

An agent $A_X$ with channel matrix $(a,b)$ requires the receiving resource $\mathcal{R}$ for its channel matrix to be unchanged. If the receiving agent only allocates $\mathcal{A},0\le \mathcal{A}\le R$ to $A_x$, the channel matrix is modified from $(a,b)$ in the following manner,

$$(a^{\mathcal{A}},b^{\mathcal{A}})=\frac{\mathcal{A}}{\mathcal{R}}(a,b)+\left(1-\frac{\mathcal{A}}{\mathcal{R}}\right)\left(\frac{a+b}{2},\frac{a+b}{2}\right).$$

(33)

Thus, $\mathcal{A}=R$ corresponds to $t=0$ above, and $\mathcal{A}=0$ corresponds to $t=1$ above. As $\mathcal{A}$ decreases, the capacity “travels” the shortest path in the Euclidean metric to the line of the 0-capacity channels. This is the essence of our modeling assumption.

Note that a channel is a 0-capacity channel iff $a=b$. However, if we let $b=a$, then $\forall \mathcal{A},(a^{\mathcal{A}},a^{\mathcal{A}})=(a,a)$.

Theorem 10.

For a non-zero channel $(a,b)$, that is, $a\ne b$, $C(a^{\mathcal{A}},b^{\mathcal{A}})$ decreases as $\mathcal{A}$ decreases from $\mathcal{R}$ to 0.

Proof. 

If $(a,b)$ is a positive channel, that is, if $a>b$, we have that $a^{\mathcal{A}}$ decreases and $b^{\mathcal{A}}$ increases as $\mathcal{A}$ goes from $\mathcal{R}$ to 0. This result is easily shown with algebra, but even more simply by observation of the line segment. From ([Theorem 4.9] [6]), if $(a,b)$ is a negative channel, then by symmetry of capacity about the line $b=a$, that completes the proof. □

Corollary 2.

If we have a 0-capacity channel $(a,b)=(e,e)$, then the $C(e^{\mathcal{A}},e^{\mathcal{A}})$ is constant at 0 as $\mathcal{A}$ decreases.

Proof. 

Trivial, since the line segment reduces to the point $(e,e)$ is this situation. □

5.1. Resource Allocation Amongst Different Transmitters

Assume that there are two transmitting agents $A_{X_1}$ with matrix $(a,b)$, and $A_{X_2}$ with matrix $(c,d)$. The difference from before is that the receiver can only allocate total resource $\mathcal{R}$ to the reception by the agents and, further, each agent requires resource $\mathcal{R}$ to prevent degradation to its channel matrix.

If $A_Y$ allocates $\mathcal{A}$ to $A_{X_1}$, we have the resulting channel matrix Equation (33) as given above. Then it allocates the remainder $\mathcal{R}-\mathcal{A}$ to $A_{X_2}$, resulting in this channel matrix

$$(c^{\mathcal{R}-\mathcal{A}},d^{\mathcal{R}-\mathcal{A}})=\left(1-\frac{\mathcal{A}}{\mathcal{R}}\right)(c,d)+\frac{\mathcal{A}}{\mathcal{R}}\left(\frac{c+d}{2},\frac{c+d}{2}\right).$$

(34)

Note that

$$\begin{array}{ccc}\hfill (a^{\mathcal{R}},b^{\mathcal{R}})& =& (a,b),\mathrm{with}C(a^{\mathcal{R}},b^{\mathcal{R}})=C(a,b),\mathrm{and}\hfill \\ \hfill (a^0,b^0)& =& \left(\frac{a+b}{2},\frac{a+b}{2}\right),\mathrm{with}C(a^0,b^0)=0.\hfill \end{array}$$

As we have shown in the previous section, we arrive at:

$$M_2^{1,2}{\mid }_{\mathcal{A}}=\left(\begin{array}{cccc}{a}^{\mathcal{A}}·c^{\mathcal{R}-\mathcal{A}}& a^{\mathcal{A}}·\overline{c^{\mathcal{R}-\mathcal{A}}}& \overline{a^{\mathcal{A}}}·c^{\mathcal{R}-\mathcal{A}}& \overline{a^{\mathcal{A}}}·\overline{c^{\mathcal{R}-\mathcal{A}}}\\ b^{\mathcal{A}}·d^{\mathcal{R}-\mathcal{A}}& b^{\mathcal{A}}·\overline{d^{\mathcal{R}-\mathcal{A}}}& \overline{b^{\mathcal{A}}}·d^{\mathcal{R}-\mathcal{A}}& \overline{b^{\mathcal{A}}}·\overline{d^{\mathcal{R}-\mathcal{A}}}\end{array}\right).$$

(35)

Consider the situation when all of the resource is allocated to one channel; then, without the loss of generality, we let $\mathcal{A}=\mathcal{R}$, giving

$$M_2^{1,2}{\mid }_{\mathcal{A}=\mathcal{R}}=\left(\begin{array}{cccc}a\left(\frac{c+d}{2}\right)& a\left(1-\frac{c+d}{2}\right)& \overline{a}\left(\frac{c+d}{2}\right)& \overline{a}\left(1-\frac{c+d}{2}\right)\\ b\left(\frac{c+d}{2}\right)& b\left(1-\frac{c+d}{2}\right)& \overline{b}\left(\frac{c+d}{2}\right)& \overline{b}\left(1-\frac{c+d}{2}\right)\end{array}\right).$$

(36)

Keep in mind that the above result is the channel matrix when we combine a 0-capacity channel with $(a,b)$. Intuitively, this should not change the capacity from that of $C(a,b)$. Looking at the channel matrix and thinking in terms of coding, we see that we are affecting the first and second outputs; as much as the third and fourth. Below, we present the mathematical details.

Theorem 11.

$C\left(M_2^{1,2}{\mid }_{\mathcal{A}=\mathcal{R}}\right)=C(a,b)$.

Proof. 

Let us calculate $C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)$. We let $\frac{c+d}{2}:=\gamma$ and $q:=(ax+b\overline{x})$. Thus,

$$(y_1,y_2,y_3,y_4)=\left(\gamma (ax+b\overline{x}),\overline{\gamma }(ax+b\overline{x}),\gamma (\overline{a}x+\overline{b}\overline{x}),\overline{\gamma }(\overline{a}x+\overline{b}\overline{x})\right).\mathrm{Then}\mathrm{if}$$

$$(y_1,y_2,y_3,y_4)=\left(\gamma q,\overline{\gamma }q,\gamma \overline{q},\overline{\gamma }\overline{q}\right),\mathrm{we}\mathrm{find}\mathrm{that}$$

$$H\left(Y\right)=h\left(\gamma \right)+h\left(q\right).$$

Next we examine the conditional entropy:

$$H\left(Y\right|X)=-x\left(a\gamma log\left(a\gamma \right)+a\overline{\gamma }log\left(a\overline{\gamma }\right)+\overline{a}\gamma log\left(\overline{a}\gamma \right)+\overline{a}\overline{\gamma }log\left(\overline{a}\overline{\gamma }\right)\right).$$

Again use the rule that the log of a product is the sum of the logs to arrive at:

$$H\left(Y\right|X)=H\left(Y\right)-H\left(Y\right|X)=h(ax+b\overline{x})-xh\left(a\right)-\overline{x}h\left(b\right).$$

This result is the same as the mutual information of $(a,b)$. Thus, the maximum of the mutual information for both cases remains the same. □

Corollary 3.

$C\left(M_2^{1,2}{\mid }_{\mathcal{A}=0}\right)=C(c,d)$.

Proof. 

If we swap the two transmitting agents we establish the proof (details are left to the reader). □

Note that any 0-capacity channel is some $(a,b)$ channel witha 0 resource allocation. Thus,

Corollary 4.

Combining $(a,b)$ with a 0-capacity channel results in a channel with the same capacity as $(a,b)$.

We arrive at the question at hand—what happens with a partial allocation to each channel? That is, in general, how does $C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)$ compare to $C(a,b)$ and $C(c,d)$? Our answer follows.

Allocate Resources to $(a,b)$ and a 0-Capacity Channel

In this situation, we know that $C\left(M_2^{1,2}{\mid }_{\mathcal{A}=\mathcal{R}}\right)=C(a,b)$ and that $C\left(M_2^{1,2}{\mid }_{\mathcal{A}=0}\right)=C(c,d)$. What happens for $0<\mathcal{A}<R$? Not surprisingly, we get the following theorem:

Theorem 12.

Through allocation if we combine $(a,b)$, the first channel, with $(e,e)$, the second channel, we find that $C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)=C(a^{\mathcal{A}},b^{\mathcal{A}})$.

Proof. 

Trivial from Theorem 9. □

5.2. More Examples

We will find the capacity of $C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)$ by using (35) for various $\mathcal{A}$ and agent matrices.

$$\begin{array}{ccc}\hfill EXAMPLE& & \mathrm{Given}\mathrm{a}90/10\mathrm{allocation}\hfill \\ \hfill \mathrm{The}\mathrm{first}\mathrm{agent}{M}_1^1=(0.8,0.4),& & \mathrm{the}\sec \mathrm{ond}\mathrm{agent}{M}_1^2=(0.7,0.3),\mathcal{A}=0.9\hfill \\ \hfill C\left(M_1^1\right)& =& 0.1246,C\left(M_1^2\right)=0.1187\hfill \\ \hfill (a^{\mathcal{A}},b^{\mathcal{A}})& =& (0.78,0.42)\hfill \\ \hfill (c^{\mathcal{R}-\mathcal{A}},c^{\mathcal{R}-\mathcal{A}})& =& (0.52,0.48)\hfill \\ \hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)& =& 0.1012\hfill \\ \hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<C\left(M_1^1\right)& & C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<C\left(M_1^2\right)\hfill \end{array}$$

$$\begin{array}{ccc}\hfill EXAMPLE& & \mathrm{Given}\mathrm{a}10/90\mathrm{allocation},\mathrm{with}\mathrm{the}\mathrm{same}\mathrm{agents}\mathrm{as}\mathrm{above}\hfill \\ \hfill \mathrm{The}\mathrm{first}\mathrm{agent}{M}_1^1=(0.8,0.4),& & \mathrm{the}\sec \mathrm{ond}\mathrm{agent}{M}_1^2=(0.7,0.3),\mathcal{A}=0.1\hfill \\ \hfill C\left(M_1^1\right)& =& 0.1246,C\left(M_1^2\right)=0.1187\hfill \\ \hfill (a^{\mathcal{A}},b^{\mathcal{A}})& =& (0.62,0.58)\hfill \\ \hfill (c^{\mathcal{R}-\mathcal{A}},c^{\mathcal{R}-\mathcal{A}})& =& (0.68,0.32)\hfill \\ \hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)& =& 0.0967\hfill \\ \hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<C\left(M_1^1\right)& & C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<C\left(M_1^2\right)\hfill \end{array}$$

$$\begin{array}{ccc}\hfill EXAMPLE& & \mathrm{Given}\mathrm{a}90/10\mathrm{allocation},\sec \mathrm{ond}\mathrm{agent}\mathrm{has}\mathrm{little}\mathrm{noise}\hfill \\ \hfill \mathrm{The}\mathrm{first}\mathrm{agent}{M}_1^1=(0.7,0.3),& & \mathrm{the}\sec \mathrm{ond}\mathrm{agent}{M}_1^2=(0.99,0.01),\mathcal{A}=0.9\hfill \\ \hfill C\left(M_1^1\right)& =& 0.1287,C\left(M_1^2\right)=0.9192\hfill \\ \hfill (a^{\mathcal{A}},b^{\mathcal{A}})& =& (0.6,0.4)\hfill \\ \hfill (c^{\mathcal{R}-\mathcal{A}},c^{\mathcal{R}-\mathcal{A}})& =& (0.745,0.255)\hfill \\ \hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)& =& 0.2030\hfill \\ \hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)>C\left(M_1^1\right)& & C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<C\left(M_1^2\right)\hfill \end{array}$$

From these results, we see that both

$$\begin{array}{c}\hfill C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<min\left(C\left(M_1^1\right),C\left(M_1^2\right)\right),\mathrm{and}\\ \hfill min\left(C\left(M_1^1\right),C\left(M_1^2\right)\right)<C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)<max\left(C\left(M_1^1\right),C\left(M_1^2\right)\right)\end{array}$$

are possible. In fact, equalities are also possible by using the special cases examined at the beginning of this section. However, $max\left(C\left(M_1^1\right),C\left(M_1^2\right)\right)<C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)$ is not possible. (We show this by a re-wording and then proving that $\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)$ cannot be larger than both $C\left(M_1^1\right)$ and $C\left(M_1^2\right)$.) Thus, we need a lemma.

Lemma 1.

For channels $(a,b)$ and $(c,d)$, we find that

$$C\left(\right(a,b)\otimes (c,d\left)\right)\le C(a,b)+C(c,d),$$

(37)

with equality if $a=b$ or $c=d$.

Proof. 

The product channel $(a,b)\times (c,d)$ is given by channel matrix

$$\left(\begin{array}{cccc}ac& a\overline{c}& \overline{a}c& \overline{a}\overline{c}\\ ad& a\overline{d}& \overline{a}d& \overline{a}\overline{d}\\ bc& b\overline{c}& \overline{b}c& \overline{b}\overline{c}\\ bd& b\overline{d}& \overline{b}d& \overline{b}\overline{d}\end{array}\right).$$

The capacity of this product channel equals the sum of the capacities of its component channels $(a,b)$ and $(c,d)$ (p. 85 [5]). Removing the middle two rows gives us $(a,b)\otimes (c,d)$, and, since removing a row never increases capacity, we find that

$$C\left(\right(a,b)\otimes (c,d\left)\right)\le C\left(\right(a,b)\times (c,d\left)\right)=C(a,b)+C(c,d).$$

□

Theorem 13.

If we combine through an allocation $(a,b)$, the first channel, with $(c,d)$, the second channel, then $C\left(M_2^{1,2}{|}_{\mathcal{A}}\right)$ cannot be greater than both of the individual channel’s component capacities.

Proof. 

Let

$$M_1^1{|}_{\mathcal{A}}=\left(\begin{array}{cc}{a}^{\mathcal{A}}& \overline{a^{\mathcal{A}}}\\ b^{\mathcal{A}}& \overline{b^{\mathcal{A}}}\end{array}\right),$$

$$M_1^2{|}_{\mathcal{R}-\mathcal{A}}=\left(\begin{array}{cc}{c}^{\mathcal{R}-\mathcal{A}}& \overline{c^{\mathcal{R}-\mathcal{A}}}\\ d^{\mathcal{R}-\mathcal{A}}& \overline{d^{\mathcal{R}-\mathcal{A}}}\end{array}\right),$$

so that $M_2^{1,2}{|}_{\mathcal{A}}=M_1^1{{|}_{\mathcal{A}}\otimes M_1^2|}_{\mathcal{R}-\mathcal{A}}$. For any input probability distribution held constant, the mutual information is convex with respect to the elements of the channel matrix ([Theorem 2.7.4] [4]). That is, for any given input probability distribution x, for all $a_1,a_2,b_1,b_2,t\in [0,1]$,

$$I(t{a}_1+\overline{t}{a}_2,t{b}_1+\overline{t}{b}_2,x)\le t·I(a_1,b_1,x)+\overline{t}·I(a_2,b_2,x),$$

where $I(\alpha ,\beta ,x)$ is the mutual information of channel $(\alpha ,\beta )$ with input distribution x; thus,

$$C(\alpha ,\beta )=\underset{x}{max}I(\alpha ,\beta ,x),\mathrm{and}$$

$$\therefore \forall x,C(\alpha ,\beta )\ge I(\alpha ,\beta ,x).$$

If we let $a_1=a,b_1=b,a_2=b_2=\frac{a+b}{2},t=\frac{\mathcal{A}}{\mathcal{R}}$, we have from convexity that

$$\begin{array}{ccc}\hfill I(a^{\mathcal{A}},b^{\mathcal{A}},x)& =& I\left(\frac{\mathcal{A}}{\mathcal{R}}a+(1-\frac{\mathcal{A}}{\mathcal{R}})\left(\frac{a+b}{2}\right),\frac{\mathcal{A}}{\mathcal{R}}b+(1-\frac{\mathcal{A}}{\mathcal{R}})\left(\frac{a+b}{2}\right),x\right)\hfill \\ & \le & \frac{\mathcal{A}}{\mathcal{R}}I(a,b,x)+(1-\frac{\mathcal{A}}{\mathcal{R}})I\left(\frac{a+b}{2},\frac{a+b}{2},x\right)\left(\mathrm{this}\mathrm{last}\mathrm{term}\mathrm{is}0\right)\hfill \end{array}$$

for any input probability distribution x, because $I(e,e,x)$ always equals 0. Now, we let $\chi$ be a capacity achieving input probability (unique except for 0-channels) distribution for $(a^{\mathcal{A}},b^{\mathcal{A}})$, giving

$$C(a^{\mathcal{A}},b^{\mathcal{A}})=I(a^{\mathcal{A}},b^{\mathcal{A}},\chi )\le \frac{\mathcal{A}}{\mathcal{R}}I(a,b,\chi )\le \frac{\mathcal{A}}{\mathcal{R}}C(a,b).$$

Therefore,

$$C\left(M_1^1{|}_{\mathcal{A}}\right)\le \frac{\mathcal{A}}{\mathcal{R}}C\left(M_1^1\right),$$

and by replacing $\frac{\mathcal{A}}{\mathcal{R}}$ with $1-\frac{\mathcal{A}}{\mathcal{R}}$ and repeating the above convexity argument, we find that

$$C\left(M_1^2{|}_{\mathcal{R}-\mathcal{A}}\right)\le \frac{\mathcal{R}-\mathcal{A}}{\mathcal{R}}C\left(M_1^2\right).$$

By Lemma 1,

$$C\left(M_2^{1,2}{|}_{\mathcal{A}}\right)=C(M_1^1{|}_{\mathcal{A}}\otimes M_1^2{|}_{\mathcal{R}-\mathcal{A}})\le C\left(M_1^1{|}_{\mathcal{A}}\right)+C\left(M_1^2{|}_{\mathcal{R}-\mathcal{A}}\right).\mathrm{Thus},$$

$$C\left(M_2^{1,2}{|}_{\mathcal{A}}\right)\le \frac{\mathcal{A}}{\mathcal{R}}C\left(M_1^1\right)+\frac{\mathcal{R}-\mathcal{A}}{\mathcal{R}}C\left(M_1^2\right)\le \left(\frac{\mathcal{A}}{\mathcal{R}}+\frac{\mathcal{R}-\mathcal{A}}{\mathcal{R}}\right)max(C\left(M_1^1\right),C\left(M_1^2\right)).$$

$$\mathrm{Resulting}\mathrm{in},C\left(M_2^{1,2}{|}_{\mathcal{A}}\right)\le max(C\left(M_1^1\right),C\left(M_1^2\right)).$$

□

Thus, we have shown that $C\left(M_2^{1,2}{\mid }_{\mathcal{A}}\right)\le max\left(C\left(M_1^1\right),C\left(M_1^2\right)\right)$ and, by using Theorem 11 and Corollary 3, equality can be obtained by letting $\mathcal{A}=\mathcal{R}$ or 0, the choice depending on the underlying original channels.

Results and Discussion

In this section, we showed what happens when we have limited transmission power and want to distribute it among two transmitting agents. The theorems of this section capture the physical properties of the power allocation and happily agree with intuition.

6. Conclusions

We considered the use of Shannon information theory, and its various entropic terms to aid in reaching optimal decisions that should be made in a multi-agent/Team scenario. Our metric for agents passing information are classical Shannon channel capacity. Our results are the mathematical theorems in this article showing how combining agents influences the channel capacity.

We have put the idea forward of multi-agent communication on a firm information theoretic foundation. We examined simple scenarios in this paper to lay that strong foundation. We obtained results that may seem obvious, but are quite difficult to prove. We ask the reader to keep in mind that there is a big difference between “it is obvious” and “it has been shown”.

From our perspective we have shown that, except for certain boundary cases, one can achieve near perfect transmission of Shannon information, provided one has a large enough number of agents.

We have used most information versus resource (power) allocation as an optimizing criterion. With regard to resource allocation, our results tell us that the best thing to do is to just use the strongest channel. This result is not surprising. However, without the mathematics to prove it, we would be relying on intuition. Furthermore, note that we only used a simple linear allocation scheme in this section, and we only combined two agents. Future work will consider non-linear allocation schemes and multiple agents to continue what we have started in this paper. Going forward, this path is especially meaningful if we adjust the Riemannian metric to influence the power allocated to each channel. For example, a geometric region with high noise levels can be reflected in the Riemannian metric by acknowledging that the $E,F,G$ terms of the metric are functions of a and b. We will explore this direction in future work.

In addition, in future work, we will also consider more than two agents competing for the available resources, non-Euclidean Riemannian metrics, and more complicated signaling alphabets and schemes. We are also interested in information flow in the Vicsek [19] bird flocking model.

7. Notation

We include some of the notation that is used repeatedly throughout the article. The other notation is variants of what we give here with changes to the indices and is made clear in its first usage.

MAS	Multi-agent System
$A_x$	Agent X
M	A channel matrix, that is every row contains non-negative numbers that sum to 1
$M_n$	2 × 2n channel matrix, representing n (transmitting) Agents
$H\left(V\right)$	Entropy of the (discrete) random variable V
$H\left(V\right|W)$	Conditional Entropy of the random variable V conditioned on W
$I(V,W)$	Mutual information between the random variables V and W
C	Capacity of a generic channel
$C_{2,2}$	Specifically the capacity of a 1 (transmitting) agent channel
$M_1^1$	A specific 1-agent channel $\left(\begin{array}{cc}a& \overline{a}\\ b& \overline{b}\end{array}\right)$. Note: C(a,b):=C($M_1^1$)
$M_1^2$	Another 1-agent channel $\left(\begin{array}{cc}c& \overline{c}\\ c& \overline{d}\end{array}\right)$
$M_2^{1,2}$	The combined channel ($a,b$) ⊗ ($c,d$) with channel matrix $\left(\begin{array}{cccc}ac& a\overline{c}& \overline{a}c& \overline{a}\overline{c}\\ bd& b\overline{d}& \overline{b}d& \overline{b}\overline{d}\end{array}\right)$
$M_2^{1,2}{\mid }_{\mathcal{A}}$	Combined power allocated channel with channel matrix
	$=\left(\begin{array}{cccc}{a}^{\mathcal{A}}·c^{\mathcal{R}-\mathcal{A}}& a^{\mathcal{A}}·\overline{c^{\mathcal{R}-\mathcal{A}}}& \overline{a^{\mathcal{A}}}·c^{\mathcal{R}-\mathcal{A}}& \overline{a^{\mathcal{A}}}·\overline{c^{\mathcal{R}-\mathcal{A}}}\\ b^{\mathcal{A}}·d^{\mathcal{R}-\mathcal{A}}& b^{\mathcal{A}}·\overline{d^{\mathcal{R}-\mathcal{A}}}& \overline{b^{\mathcal{A}}}·d^{\mathcal{R}-\mathcal{A}}& \overline{b^{\mathcal{A}}}·\overline{d^{\mathcal{R}-\mathcal{A}}}\end{array}\right)$
$M_{2-}$	= $\left(\begin{array}{ccc}{a}^2& 2\overline{a}a& {\overline{a}}^2\\ b^2& 2\overline{b}b& {\overline{b}}^2\end{array}\right)$, formed from the ($a,b$) channel