# Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $$X_i \in \mathcal X$$ the input at time $$i$$ and by $$Y_i \in \mathcal Y$$ the output at time $$i$$.

Assume the channel is not memoryless and $$Y_i$$ depends on some of the previous inputs and/or outputs in a particular way (that is the same through all $$i$$). For example, $$Y_i$$ might depend on $$X_i$$ as well as $$X_{i-1}$$ through transition probabilities $$P_{Y|X,X'}(\cdot|\cdot,\cdot)$$ for all $$i$$ (where $$X'$$ represents the input at the previous transmission). For another example, $$Y_i$$ might depend on $$X_i$$ as well as $$Y_{i-1}$$ through transition probabilities $$P_{Y|X,Y'}(\cdot|\cdot,\cdot)$$ for all $$i$$ (where $$Y'$$ represents the output after the previous transmission).

We study the input-output relations of $$n$$ consecutive channel uses. $$\{ X_i \}_{i=1}^n$$ are the inputs and $$\{ Y_i \}_{i=1}^n$$ are the corresponding outputs. We represent the dependency relations of these by a graph with $$2n$$ nodes (one for each $$X_i$$ and for each $$Y_i$$), where there is a directed edge whenever there is a dependency. See the examples in the figures below.

Figure 1

Figure 2

Figure 3

Call this graph the dependency graph of the channel.

My question is: Are there works in the literature where channel capacity or other quantities of the channel are studied in connection with the properties of its dependency graph?

• Throwing away the actual channel matrix changes the model from a probabilistic to a possibilistic one. Taint analysis could take care of that. Have you checked for sources on that topic?
– Kai
Commented May 18 at 12:08
• It is not quite "throwing away the actual channel matrix". The catch is that the channel is not necessarily memoryless. At transmission $n$, the output $Y_n$ might be depending on $X_n$ as well as other quantities (such as $X_{n-1}$ and/or $Y_{n-1}$). There is still a transition matrix; it is just larger. Instead of $P_{Y|X}$, we would have transition probabilities for instance of the form $P_{Y|X,X'}$ or $P_{Y|X,Y'}$ (where $X'$ represents the previous output and $Y'$ represents the previous output, if the current output depends on them) Commented May 20 at 23:32