4. Measurement

This section adapts Definition 1 (http://planetmath.org/1introduction#Thmdefn1)to distributedstochastic systems. The first step is to replace elements ofstate space $X$ with stochastic maps $d_{in}:ℝ\to 𝒱S^{𝐃}$, or equivalently probability distributionson $S^{𝐃}$, which are the system’s inputs. Individualelements of $S^{𝐃}$ correspond to Dirac distributions.

Second, replace function $f:X\to ℝ$ with mechanism${𝔪}_{𝐃}:𝒱S^{𝐃}\to 𝒱A^{𝐃}$.Since we are interested in the compositional structure ofmeasurements we also consider submechanisms ${𝔪}_{𝐂}$.However, comparing mechanisms requires that they have the samedomain and range, so we extend ${𝔪}_{𝐂}$ to the entiresystem as follows

$${𝔪}_{𝐂}=𝒱S^{𝐃}\stackrel{𝜋}{\to }𝒱S^{𝐂}\stackrel{{𝔪}_{𝐂}}{\to }𝒱A^{𝐂}\stackrel{{\pi }^{\mathrm{♮}}}{\to }𝒱A^{𝐃}.$$(1)

We refer to the extension as ${𝔪}_{𝐂}$ by abuse of notation.We extend mechanisms implicitly whenever necessary withoutfurther comment. Extending mechanisms in this way maps thequale into a cloud of points in $\mathrm{Hom}(𝒱A^{𝐃},𝒱S^{𝐃})$ labeled by objects in ${\mathrm{𝚂𝚢𝚜}}_{𝐃}$.

In the special case of the initial object ${\perp }_{𝐃}$, define

$${𝔪}_{\perp }=𝒱S^{𝐃}\stackrel{𝜔}{\to }ℝ\stackrel{{\omega }^{\mathrm{♮}}}{\to }𝒱A^{𝐃}.$$

Remark 3.

Subsystems differing by non-existent edges (Remark 2 (http://planetmath.org/3distributeddynamicalsystems#Thmrem2))are mapped to the same mechanism by this construction, thusmaking the fact that the edges do not exist explicit withinthe formalism.

Composing an input with a submechanism yields an output$d_{out}:={𝔪}_{𝐂}\circ d_{in}:ℝ\to 𝒱A^{𝐃}$, which is a probability distribution on$A^{𝐃}$. We are now in a position to define

Definition 8.

A measuring device is the dual ${𝔪}_{𝐂}^{\mathrm{♮}}$to the mechanism of a subsystem. An output is astochastic map $d_{out}:ℝ\to 𝒱A^{𝐃}$. Ameasurement is a composition ${𝔪}_{𝐂}^{\mathrm{♮}}\circ d_{out}:ℝ\to 𝒱S^{𝐃}$.

Recall that stochastic maps of the form $ℝ\to 𝒱X$ correspond to probability distributions on $X$. Outputs asdefined above are thus probability distributions on$A^{𝐃}$, the output alphabet of $𝐃$. Individualelements of $A^{𝐃}$ are recovered as Dirac vectors:$ℝ\stackrel{{\delta }_a}{\to }𝒱A^{𝐃}$.

Definition 9.

The effective information generated by ${𝐂}_1$in the context of subsystem ${𝐂}_2\subset {𝐂}_1$ is

$$ei({𝔪}_{{𝐂}_2}\to {𝔪}_{{𝐂}_1},d_{out}):=H[{𝔪}_{{𝐂}_1}^{\mathrm{♮}}\circ d_{out}\parallel {𝔪}_{{𝐂}_2}^{\mathrm{♮}}\circ d_{out}].$$(2)

The null context, corresponding to the empty subsystem$\perp =\mathrm{\varnothing }\subset V_{𝐃}\times V_{𝐃}$, is a specialcase where ${𝔪}_{𝐂}^{\mathrm{♮}}\circ d_{out}$ is replaced by theuniform distribution ${\omega }_{𝐃}^{\mathrm{♮}}$ on $S^{𝐃}$.To simplify notation define

$$ei({𝔪}_{𝐂},d_{out}):=ei({𝔪}_{\perp }\to {𝔪}_{𝐂},d_{out}).$$

Here, $H[p\parallel q]={\sum }_i{p}_i{\log }_2\frac{p_i}{q_i}$ is theKullback-Leibler divergence or relative entropy[1]. Eq. (2) expands as

$$ei({𝔪}_{{𝐂}_2}\to {𝔪}_{{𝐂}_1},d_{out})=\sum _{s\in S^{𝐃}}⟨{𝔪}_{{𝐂}_1}^{\mathrm{♮}}\circ d_{out}|{\delta }_s⟩\cdot {\log }_2\frac{⟨{𝔪}_{{𝐂}_1}^{\mathrm{♮}}\circ d_{out}|{\delta }_s⟩}{⟨{𝔪}_{{𝐂}_2}^{\mathrm{♮}}\circ d_{out}|{\delta }_s⟩}.$$(3)

When $d_{out}={\delta }_a$ for some $a\in A^{𝐃}$ wehave

$$ei({𝔪}_{{𝐂}_2}\to {𝔪}_{{𝐂}_1},{\delta }_a)=\sum _{s\in S^{𝐃}}{p}_{{𝔪}_{{𝐂}_1}}(s|a)\cdot {\log }_2\frac{p_{{𝔪}_{{𝐂}_1}}(s|a)}{p_{{𝔪}_{{𝐂}_2}}(s|a)}.$$(4)

Definition 8 requires some unpacking. To relateit to the classical notion of measurement, Definition 1 (http://planetmath.org/1introduction#Thmdefn1),we consider system $𝐃=\left\{v_X\stackrel{𝑓}{\to }{v}_Y\right\}$where the alphabets of $v_X$ and $v_Y$ are the sets$A_{v_X}=X$ and $A_{v_Y}=Y$ respectively, and themechanism of $v_Y$ is ${𝔪}_Y=𝒱f$. In other words,system $𝐃$ corresponds to a single deterministic function$f:X\to Y$.

Proposition 5 (classical measurement).

The measurement ${\mathrm{(}\mathrm{V}\mathit{}f\mathrm{)}}^{\mathrm{♮}}\mathrm{\circ }{\delta }_y$performed when deterministic function $f\mathrm{:}X\mathrm{\to }Y$outputs $y$ is equivalent to the preimage $f^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}y\mathrm{)}$.Effective information is $e\mathit{}i\mathit{}\mathrm{(}\mathrm{V}\mathit{}f\mathrm{,}{\delta }_y\mathrm{)}\mathrm{=}{\log }_{\mathrm{2}}\mathit{}\frac{\mathrm{|}X\mathrm{|}}{\mathrm{|}{f}^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}y\mathrm{)}\mathrm{|}}$.

Proof:By Corollary 2 (http://planetmath.org/2stochasticmaps#Thmthm2)measurement ${(𝒱f)}^{\mathrm{♮}}\circ {\delta }_y$ is conditionaldistribution

which generalizes the preimage. Effective information followsimmediately.$\mathrm{■}$

Effective information can be interpreted as quantifying ameasurement’s precision. It is high if few inputs cause $f$to output $y$ out of many – i.e. $f^{-1}(y)$ has fewelements relative to $|X|$ – and conversely is low if manyinputs cause $f$ to output $y$ – i.e. if the output isrelatively insensitive to changes in the input. Precisemeasurements say a lot about what the input could have beenand conversely for vague measurements with low $ei$.

The point of this paper is to develop techniques for studyingmeasurements constructed out of two or more functions. Wetherefore present computations for the simplest case,distributed system $X\times Y\stackrel{𝑔}{\to }Z$, in considerabledetail. Let $𝐃$ be the graph

with obvious assignments of alphabets and the mechanism of$v_Z$ as ${𝔪}_Z=𝒱g$. To make the formulas more readablelet ${𝔪}_{XY}=𝒱g$, ${𝔪}_{X\bullet }=𝒱g\circ {\pi }_{XY,X}^{\mathrm{♮}}$ and ${𝔪}_{\bullet Y}=𝒱g\circ {\pi }_{XY,Y}^{\mathrm{♮}}$. We then obtain lattice

The remainder of this section and most of the next analyzesmeasurements in the lattice.

Proposition 6 (partial measurement).

The measurement performed on $X$ when $g\mathrm{:}X\mathrm{\times }Y\mathrm{\to }Z$ outputs $z$, treating $Y$ as extrinsicnoise, is conditional distribution

(5)

where $g_{x\mathrm{\times }Y}^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}z\mathrm{)}\mathrm{:=}p\mathit{}{r}_Y\mathit{}\mathrm{(}{g}^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}z\mathrm{)}\mathrm{\cap }\mathrm{\{}x\mathrm{\}}\mathrm{\times }Y\mathrm{)}$. The effective information generated by thepartial measurement is

$$ei({𝔪}_{X\bullet }^{\mathrm{♮}},{\delta }_z)={\log }_2|X|+\sum _{x\in X}p(x|z)\cdot {\log }_{2}p(x|z).{\delta }_z)|g{}^{-1}(z)|\cdot$$(6)

Proof: Treating $Y$ as a source of extrinsic noise yields$𝒱X\stackrel{{\pi }^{\mathrm{♮}}}{\to }𝒱X\otimes 𝒱Y\stackrel{𝒱g}{\to }𝒱Z$ which takes${\delta }_x\mapsto \frac{1}{|Y|}{\sum }_{y\in Y}{\delta }_{g(x,y)}$.The dual is

$${𝔪}_{X\bullet }^{\mathrm{♮}}={\pi }_{XY,X}\circ {(𝒱g)}^{\mathrm{♮}}:{\delta }_z\mapsto \sum _{x\in X}\frac{|g_{x\times Y}^{-1}(z)|}{|g^{-1}(z)|}\cdot {\delta }_x.$$

The computation of effective information follows immediately.$\mathrm{■}$

A partial measurement is precise if the preimage $g^{-1}(z)$has small or empty intersection with $\{x\}\times Y$ for most$x$, and large intersection for few $x$.

Propositions 5 and 6 computeeffective information of a measurement relative to the nullcontext provided by complete ignorance (the uniformdistribution). We can also compute the effective informationgenerated by a measurement in the context of a submeasurement:

Proposition 7 (relative measurement).

The information generated by measurement $X\mathrm{\times }Y\stackrel{𝑔}{\mathrm{\to }}Z$ in the context of the partial measurement where $Y$ is unobserved noise, is

$$ei({𝔪}_{X\bullet }\to {𝔪}_{XY},{\delta }_z)=\sum _{x\in X}\frac{g_{x\times Y}^{-1}(z)}{g^{-1}(z)}{\log }_2\frac{|Y|}{g_{x\times Y}^{-1}(z)}.$$(7)

Proof: Applying Propositions 5 and6 obtains

$$ei({𝔪}_{X\bullet }\to {𝔪}_{XY},{\delta }_z)=\sum _{(x,y)\in g^{-1}(z)}\frac{1}{|g^{-1}(z)|}{\log }_2[\frac{1}{|g^{-1}(z)|}\cdot \frac{|g^{-1}(z)|\cdot |Y|}{|g_{x\times Y}^{-1}(z)|}]$$

which simplifies to the desired expression.$\mathrm{■}$

To interpret the result decompose $X\times Y\stackrel{𝑔}{\to }Z$into a family of functions $ℛ=\left\{Y\stackrel{g_{x\times Y}}{\to }Z\right|x\in X\}$labeled by elements of $X$, where $g_{x\times Y}(y):=g(x,y)$.The precision of the measurement performed by $g_{x\times Y}$s ${\log }_2\frac{|Y|}{g_{x\times Y}^{-1}(z)}$. It follows thatthe precision of the relative measurement,Eq. (7), is the expected precision of themeasurements performed by family $ℛ$ taken withrespect to the probability distribution$p(x|z)=\frac{g_{x\times Y}^{-1}(z)}{g^{-1}(z)}$ generated bythe noisy measurement.

In the special case of $g:X\times Y\to Z$ relativeprecision is simply the difference of the precision of thelarger and smaller subsystems:

Corollary 8 (comparing measurements).

$$ei({𝔪}_{X\bullet }\to {𝔪}_{XY},{\delta }_z)=ei({𝔪}_{XY},{\delta }_z)-ei({𝔪}_{X\bullet },{\delta }_z)$$

Proof: Applying Propositions 5,6, 7 and simplifying obtains

$ei({𝔪}_{XY},{\delta }_z)-ei({𝔪}_{X\bullet },{\delta }_z)$$={\log }_2{\displaystyle \frac{|X|\cdot |Y|}{|g^{-1}(z)|}}-{\displaystyle \sum _x}{\displaystyle \frac{|g_{x\times Y}^{-1}(z)|}{|g^{-1}(z)|}}{\log }_2{\displaystyle \frac{|X|\cdot |g_{x\times Y}^{-1}(z)|}{|g^{-1}(z)|}}$

$={\log }_2{\displaystyle \frac{|Y|}{|g^{-1}(z)|}}+{\displaystyle \sum _{(x,y)\in g^{-1}(z)}}{\displaystyle \frac{1}{|g^{-1}(z)|}}{\log }_2{\displaystyle \frac{|g^{-1}(z)|}{|g_{x\times Y}^{-1}(z)|}}$

$=ei({𝔪}_{X\bullet }\to {𝔪}_{XY},{\delta }_z).\mathrm{■}$