Open Study Answer #134

As Draft PDF

Proposed answer to the following questions:

Related questions:


WORK IN PROGRESS

Distribution Decomposition

Given a set of random variables \(\{ Z_i \}_{i \in I}\) with countable index set \(I\), and probability space \(\Omega\), for each \(i \in I\), define functions \({B}_{ i}(s)\) and \(c_i(s)\) over strings of alphabet \(\{ \mathtt{0}, \mathtt{1} \}\) [1].

\[\begin{eqnarray*} {B}_{ i}(\epsilon) & := & \Omega \\ \end{eqnarray*}\] For any string \(s\) with \({ \operatorname{P}({ {B}_{ i}(s) }) > 0}\) , \[\begin{eqnarray*} c_i(s) & := & \operatorname{E}\!\left({ Z_i | {B}_{ i}(s) }\right) \\ {B}_{ i}(s \mathtt{0}) & := & {B}_{ i}(s) \cap \{ Z_i < c_i(s) \} \\ {B}_{ i}(s \mathtt{1}) & := & {B}_{ i}(s) \cap \{ Z_i > c_i(s) \} \\ \end{eqnarray*}\] otherwise \[\begin{eqnarray*} {B}_{ i}(s\ell) & := & \emptyset \\ \end{eqnarray*}\]

A new probability space \(\Omega'\) is defined by extending \(\Omega\) such that for each \(i \in I\) and string \(s \in \{ \mathtt{0}, \mathtt{1} \}^*\) with \(\operatorname{P}({ {B}_{ i}(s)}) - \operatorname{P}({ \{Z_i = c_i(s)\} }) > 0\), there are new disjoint events \(C_{i,0}(s)\) and \(C_{i,1}(s)\) such that \[\begin{eqnarray*} \{Z_i = c_i(s)\} & = & C_{i,0}(s) \cup C_{i,1}(s) \\ \end{eqnarray*}\] and for each \(\ell \in \{ \mathtt{0}, \mathtt{1} \}\) and all events \(S\) in \(\Omega\) \[\begin{eqnarray*} \operatorname{P}({ S \cap C_{i,\ell}(s) }) & = & \operatorname{P}({ S \cap \{Z_i = c_i(s)\} }) \frac{ \operatorname{P}({ {B}_{ i}(s\ell)}) }{ \operatorname{P}({ {B}_{ i}(s)})-\operatorname{P}({ \{Z_i = c_i(s)\} }) } \\ \end{eqnarray*}\] Define \[\begin{eqnarray*} B'_i(s) & := & {B}_{ i}(s) \cup C_{i,\ell}(s) \\ v_i(s) & = & \sum_{\ell \in \{ \mathtt{0}, \mathtt{1} \}} \operatorname{P}({ {B}_{ i}(s\ell)|{B}_{ i}(s)}) \left( c_i(s\ell)-c(0) \right)^2 \\ h_i(s) & = & \sum_{\ell \in \{ \mathtt{0}, \mathtt{1} \}} h({B}_{ i}(s\ell)|{B}_{ i}(s)) \\ \theta_i & := & \left\{ \{B'_i(s\mathtt{0}),B'_i(s\mathtt{1})\} \mapsto v_i(s)/h_i(s) : \operatorname{P}({ {B}_{ i}(s)}) > 0 \right\} \\ \end{eqnarray*}\]

The scope product [2]" across all \(\theta_i\) is the distribution decomposition of \(\{ Z_i \}_{i \in I}\).

TODO: scope product across countable index set

References

1. Hopcroft JE, Ullman JD (1979) Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, Mass

2. Ellerman EC Open study answer #133. http://castedo.com/osa/133/