Vertical Dependency in Sequences of Categorical Random Variables

Vertical Dependency in Sequences of Categorical Random Variables

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

Dependency Generators

Both FK-dependency and sequential dependency structures are particular examples of a class of vertical dependency structures. We denote the dependency of subsequent categorical random variables on a previous variable in the sequence as a vertical dependency. In this section, we define a class of functions that generate vertical dependency structures with the property that all the variables in the sequence are identically distributed but dependent.

Vertical Dependency Generators Produce Identically Distributed Sequences

Define the set of functions

\mathscr{C}_{\delta} = \{\alpha: \mathbb{N}_{\geq 2} \to \mathbb{N} : \alpha(n) \geq 1 \wedge \alpha(n) < n\:\: \forall\:n\}.

The mapping defines a direct dependency of n on \alpha(n), denoted n \stackrel{\delta}{\rightsquigarrow} \alpha(n). We have already defined the notion of direct dependency, but we formalize it here.

Definition. (Direct Dependency)

Let \epsilon_{m}, \epsilon_{n} be two categorical random variables in a sequence, where m < n. We say \epsilon_{n} has a direct dependency on \epsilon_{m}, denoted \epsilon_{n} \rightsquigarrow_{\delta} \epsilon_{m}, if P(\epsilon_{n}|\epsilon_{n-1},\ldots,\epsilon_{1}) = P(\epsilon_{n}|\epsilon_{m}).

Example 3.
For FK-dependence, \alpha(n) \equiv 1. That is, for any n, \epsilon_{n} \rightsquigarrow_{\delta} \epsilon_{1}

Example 4. 
The function \alpha(n) = n-1 generates the sequential dependency structure.

We now define the notion of dependency continuity.


Definition. (Dependency Continuity)
A function \alpha: \mathbb{N}_{\geq 2} \to \mathbb{N} is dependency continuous if \forall n \exists j \in \{1,...,n-1\} such that \alpha(n) = j


We require that the functions in \mathscr{C}_{\delta} be dependency continuous. Thus, the formal definition of the class of dependency generators \mathscr{C}_{\delta} is


Definition. (Dependency Generator)
We define the set of functions \mathscr{C}_{\delta} = \{\alpha : \mathbb{N}_{\geq 2} \to \mathbb{N}\} such that

  •  \alpha(n) < n
  • \forall n \exists j \in \{1,...,n-1\} : \alpha(n) = j

and refer to this class as dependency generators.

Each function in \mathscr{C}_{\delta} generates a unique dependency structure for sequences of dependent categorical random variables where the individual elements of the sequence remain identically distributed.


Theorem 2. (Identical Distribution of Sequences Generated by Dependency Generators)
Let \alpha \in \mathscr{C}_{\delta}. Then for any n\in \mathbb{N}, n \geq 2, the dependent categorical random sequence generated by \alpha has identically distributed elements.