Probability terminology: determining events based on random variable evaluations

Question

I am reading a paper right now on a constructive proof for the Lovasz Local Lemma and I want to sanity check my understanding on some of their terminology that is unfamiliar to myself. I will include a passage that illustrates what I'm concerned with:

So the first piece of terminology here I want to make sure I understand is first the discussion about the events $A$ determined by values of some subset of random variables $S$ of $\mathcal{P}$. My understanding can be expressed with an example. Suppose we have a probability space $\Omega = \lbrace \omega_1, \omega_2, \omega_3, \omega_4 \rbrace$. Further, define our set of random variables $\mathcal{P} = \lbrace X_1, X_2 \rbrace$ where we define the two random variables to be

\begin{align} X_1(\omega) &= \begin{cases} 2 & \text{if } \omega \in \lbrace \omega_1, \omega_2 \rbrace \\ 1 & \text{if } \omega \in \lbrace \omega_3 \rbrace \\ 0 & \text{otherwise} \end{cases} \\ X_2(\omega) &= \begin{cases} 1 & \text{if } \omega \in \lbrace \omega_2 \rbrace \\ 0 & \text{otherwise} \end{cases} \end{align}

Now my suspicion is an event $A$ is determined by some set of random variables $\lbrace X_1, X_2 \rbrace$ by making $A$ equal to the intersection of the events that make $X_1$ and $X_2$ output some values. So for example, if $X_1 = 2$ and $X_2 = 1$, we would say the event $A$ determined by the values of these two random variables is $A = \lbrace \omega_1, \omega_2 \rbrace \cap \lbrace \omega_2 \rbrace = \lbrace \omega_2 \rbrace$. It is also appears that within this example, $\lbrace X_2 \rbrace \subset \mathcal{P}$ is a minimal subset needed to determine $A$, so it seems that $\text{vbl}(A) = \lbrace X_2 \rbrace$. Is all of this correct so far?

Also, I just want to make sure I understand their use of "evaluating" a random variable. Is an evaluation of a random variable really just choosing a value for it? So if I choose $X_1 = 1$, that's an evaluation of the random variable $X_1$? If so, it seems the passage is saying that an evaluation of a set $S$ of random variables violates $A$ if we have some evaluation for the random variables and this evaluation determines some event $\mathcal{E}$ such that $\mathcal{E} \subseteq A$, since this determined event should imply that $A$ should happen. Does this seem reasonable? If so, I do not think I understand why they claim there's a unique minimal subset that determines $A$. Seems to me there need not be a unique minimal subset but that there could be multiple subsets that achieve the smallest cardinality possible that can determine $A$ with an appropriate evaluation. Thus, I suspect I am understanding their terminology incorrectly.

Any help one can provide to help me understand the terminology and few concepts would be great.

Answer 1

My interpretation is that "$A$ is determined by $S$" simply means this: if you know the values of each $X_i \in S = \{X_1, X_2, \dots, X_k\}$, then you can tell whether $A$ has happened or not. If you prefer, think of the $\{0,1\}$-valued indicator variable for event $A$, which I will denote $1_A$. Then "$A$ is determined by $S$" means there exists a (deterministic) function $f: \mathbb{R}^k \to \{0,1\}$ s.t. $1_A = f(X_1, X_2, \dots, X_k)$ (with certainty, i.e. for any sample point).

In particular, an evaluation of $S$ would be $(x_1, x_2, \dots, x_k) \in \mathbb{R}^k$, interpreted as values taken by $(X_1, X_2, \dots, X_k)$ respectively. And this evaluation violates $A$ iff $f(x_1, x_2, \dots, x_k) = 1$.

$A$ does not need to be an intersection of events of the form $X_k \in \mathcal{X}_k$, where $\mathcal{X}_k$ is some subset of $\mathbb{R}$. E.g. in your example $A = \{\omega_2\}$ is determined by $X_2$, but another event $B = \{\omega_1, \omega_3\}$ would be determined by $\{X_1, X_2\}$ and that is the minimal set for $B$. In this case, $B$ is not an intersection of events of the form $X_k \in \mathcal{X}_k$, but rather a union of several such intersections, $B = (X_1 = 1) \cup ((X_1 = 2) \cap (X_2 = 0))$. So if you prefer, "$A$ is determined by $S$" can equivalently be considered to mean: $A$ can be written as a logical formula where each "atomic" term is an event of the form $(X_k \in \mathcal{X}_k)$ for some $X_k \in S$. The logical formula is allowed to use any combination of AND, OR, NOT.

As for the "unique minimal subset", this is a consequence of the $X_k$'s being mutually independent! If they were dependent, then the minimal subset may not be unique. E.g. add $X_3 = X_2$ to your example, thereby violating independence, and you now have $A$ being determined by $\{X_2\}$, and also by $\{X_3\}$, so you have two such minimal subsets (i.e. not unique). For a less trivial example, consider flipping two coins and the indicator variables for the events "first coin Heads", "second coin Heads", and "two results are the same". The event "both Heads" is determined by any $2$ out of the $3$ indicator variables, so the minimal subset has size $2$ but is not unique. Note that in this example the three r.v.s are pairwise independent, but not mutually independent.

However, when the r.v.s are mutually independent, then informally speaking, the event $X_k \in \mathcal{X}_k$ cannot be written as a formula using all the other r.v.s, so if $X_k$ is in a minimal determining subset then it must be in any determining subset. I'm not sure how to prove this rigorously, to be honest, so while I agree with the authors that in this case the minimal subset must be unique, I might not go so far as to say "Clearly" it must be unique. :)