# Vertical Dependency in Sequences of Categorical Random Variables

##### For the full text, including proofs, download the pdf here.

### Graphical Interpretation and Illustrations

We may visualize the dependency structures generated by \alpha \in \mathscr{C}_{\delta} via directed *dependency graphs*. Each \epsilon_{n} represents a vertex in the graph, and a directed edge connects n to \alpha(n) to represent the direct dependency generated by \alpha. This section illustrates some examples and gives a graphical interpretation of the result in Theorem 2.

**First-Kind Dependency**

For FK-dependency, \alpha(n) \equiv 1 generates the graph above. Each \epsilon_{i} depends directly on \epsilon_{1}, and thus we see no connections between any other vertices i, j where j \neq 1. There are n-1 separate subsequences of length 2 in this graph.

**Sequential Dependency**

**A Monotonic Example**

Here, \alpha(n) = \lfloor \sqrt{n}\rfloor gives an example of a monotonic function in \mathscr{C}_{\delta} and the dependency structure it generates. Again, note that any n has a path to 1, and the number of subsequences is between 1 and n-1.

**A Nonmonotonic Example**

Here, \alpha(n)=\left\lfloor\frac{\sqrt{n}}{2}\left(\sin(n)\right)+\frac{n}{2}\right\rfloor illustrates a more contrived example where the function is nonmonotonic. It is neither increasing nor decreasing. The previous examples have all been nondecreasing.

**A Prime Example**

Let \alpha \in \mathscr{C}_{\delta} be defined in the following way. Let p_{m} be the mth prime number, and let \{kp_{m}\} be the set of all postive integer multiples of p_{m}. Then the set \mathscr{P}_{m} = \{kp_{m}\} \setminus \cup_{i=1}^{m-1}\{kp_{i}\} gives a disjoint partitioning of \mathbb{N}. That is, \mathbb{N} = \sqcup_{m}\mathscr{P}_{m}, and thus for any n \in \mathbb{N}, n \in \mathscr{P}_{m} for exactly one m. Now let \alpha(n) = m. Thus, the function is well-defined. We may write \alpha: \mathbb{N}_{\geq 2} \to \mathbb{N} as \alpha[\mathscr{P}_{m}] = \{m\}. As an illustration,

\begin{aligned}\alpha[\{2k\}] &= \{1\} \\\alpha[\{3k\}\setminus \{2k\}] &= \{2\} \\\alpha[\{5k\}\setminus (\{2k\}\cup \{3k\})] &= \{3\} \\&\qquad\vdots\\\alpha[\{kp_{m}\}\setminus (\cup_{i=1}^{m-1}\{kp_{i}\})] &= \{m\}\end{aligned}