Directed Graph Distributions

Why

We want to visualize the probabilistic relations between components of outcomes in probabilistic models over large (e.g., product) outcome sets.¹

Definition

Suppose $X_1, \dots , X_k$ are sets. Define $X = \prod_{i = 1}^k X_i$. For $x \in X$ and $S \subset \set{1, \dots , n}$, denote the subvector of $x$ indexed (in order) by $S$ by $x_S$.²

A distribution $p: X \to [0, 1]$ factors according to a directed graph on $\set{1, \dots , n}$ with parent function $\pa: \set{1,\dots ,n} \to \powerset{\set{1, \dots , n}}$ if

\[ p(x) = \prod_{\pa_i = \varnothing} g_i(x_i) \prod_{\pa_i \neq \varnothing} g_{i}(x_i, x_{\pa_i}), \]

where $g_i$ is a distribution for all $i$ which $\pa_i = \varnothing$ and $g_{i}(\cdot , \xi )$ is a distribution for all $\xi \in \prod_{j \in \pa_i} A_j$, $i$ for which $\pa_i \neq \varnothing$.

Examples

Consider a rooted tree distribution (see Rooted Tree Distributions), or a memory chain (see Memory Chains), or a hidden memory chain (see Hidden Memory Chains).⁴

---

1. Future editions will modify and expand. The title of the sheet may change, since another interpretation for the words “directed graph distribution” is a distribution on directed graphs. ↩︎
2. Future editions will rework this treatment, perhaps combining it with the sheet Index Matrices, which will possibly be split up. ↩︎
3. Future editions will be precise and give an account. ↩︎
4. Future editions will expand. ↩︎