Revealing Coordinates One at a Time
Suppose an outcome of interest depends on several independent random inputs, but the inputs become available sequentially. At each stage, the information already revealed determines some of the outcome while uncertainty about the remaining coordinates is averaged out. The resulting conditional expectations form a martingale: before the next coordinate is seen, the expected value of the updated estimate equals the current estimate.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(X_1,\ldots,X_m\) be independent random elements, with \(X_r\) taking values in a measurable space \(E_r\) and having distribution \(\mu_r\). Let \(f:E_1\times\cdots\times E_m\to\mathbb{R}\) be measurable, and assume \(\mathbb{E}|f(X_1,\ldots,X_m)|<\infty\). Define the information available after revealing the first \(k\) coordinates by \(\mathcal{F}_k=\sigma(X_1,\ldots,X_k)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). The process below has discrete time index \(k=0,\ldots,m\) and real state space \(S=\mathbb{R}\).
Independence makes the conditional expectations concrete. Once \(X_1,\ldots,X_k\) are known, average \(f\) over the independent distributions of all remaining coordinates. For \(k=m\), there are no remaining coordinates to average over; for \(k=0\), average over all of them.
Proof. Independence implies that the joint distribution of \((X_1,\ldots,X_m)\) is the product measure \(\mu_1\otimes\cdots\otimes\mu_m\). By Fubini's theorem, for almost every prefix \((x_1,\ldots,x_k)\), the section of \(f\) is integrable over the remaining coordinates. Define \(g_k\) by the displayed integral on those prefixes, and assign it any fixed value, say zero, on the exceptional set. That set has prefix-distribution measure zero, so the assignment does not affect \(g_k(X_1,\ldots,X_k)\) almost surely. Also, integrating the absolute value of the section and using the product measure gives \(\mathbb{E}|g_k(X_1,\ldots,X_k)|\leq\mathbb{E}|f(X_1,\ldots,X_m)|<\infty\). For any \(A\in\mathcal{F}_k\), there is a measurable set \(C\subseteq E_1\times\cdots\times E_k\) such that \(A=\{(X_1,\ldots,X_k)\in C\}\). Integrating first over the remaining coordinates gives $$ \mathbb{E}[\mathbf{1}_A f(X_1,\ldots,X_m)] =\int_C g_k(x_1,\ldots,x_k)\prod_{r=1}^k\mu_r(dx_r) =\mathbb{E}[\mathbf{1}_A g_k(X_1,\ldots,X_k)]. $$ This identity for every \(A\in\mathcal{F}_k\), together with \(\mathcal{F}_k\)-measurability and integrability, is the defining property of conditional expectation. It proves the formula, including \(k=0\) and \(k=m\), where the prefix or remaining-coordinate product is empty. \(\square\)
Proof. The averaging formula makes \(M_k\) a function of \(X_1,\ldots,X_k\), so it is \(\mathcal{F}_k\)-measurable. The theorem above shows that it is integrable. Fix \(k\geq1\) and take any \(A\in\mathcal{F}_{k-1}\). Integrating \(g_k\) first over \(X_{k+1},\ldots,X_m\), and then over \(X_k\), gives $$ \mathbb{E}[\mathbf{1}_A M_k] =\int_{\{(x_1,\ldots,x_{k-1})\in C\}} \left(\int g_k(x_1,\ldots,x_k)\,\mu_k(dx_k)\right) \prod_{r=1}^{k-1}\mu_r(dx_r) =\mathbb{E}[\mathbf{1}_A M_{k-1}], $$ where \(C\) is a measurable prefix set representing \(A\). The inner integral is \(g_{k-1}\), because it averages over coordinate \(k\) as well as all later coordinates. The equality for every \(A\in\mathcal{F}_{k-1}\) is the defining property of \(\mathbb{E}[M_k\mid\mathcal{F}_{k-1}]\). Hence this conditional expectation equals \(M_{k-1}\) almost surely. \(\square\)
The theorems explain why the construction works: independence supplies the product distribution used in the averaging, and conditional expectation supplies the martingale identity. The examples below calculate these averages directly, rather than relying on the identity alone.
Worked Example: An Indicator of a Majority
Let \(X_1,X_2,X_3\) be independent fair coin indicators, so each takes values \(0\) and \(1\) with probability \(\tfrac12\). On their product probability space, use the filtration \(\mathcal{F}_k=\sigma(X_1,\ldots,X_k)\) and let \(f=\mathbf{1}_{\{X_1+X_2+X_3\geq2\}}\). Find \(M_0,M_1,M_2,M_3\).
There are eight equally likely triples, and four have at least two ones, so \(M_0=\mathbb{E}f=\tfrac48=\tfrac12\). After revealing \(X_1=0\), the remaining two coordinates must both be \(1\), an event with probability \(\tfrac12\cdot\tfrac12=\tfrac14\). After revealing \(X_1=1\), at least one of the remaining two must be \(1\), which has probability \(1-\tfrac12\cdot\tfrac12=\tfrac34\). Thus \(M_1=\tfrac14\) when \(X_1=0\), and \(M_1=\tfrac34\) when \(X_1=1\).
After two coordinates are revealed, the conditional probabilities are \(0\) for prefix \(00\), \(\tfrac12\) for prefix \(01\), \(\tfrac12\) for prefix \(10\), and \(1\) for prefix \(11\). These values follow by checking whether the last fair coin must be \(1\), can be either value, or is no longer needed. After all three are revealed, \(M_3=f\): it is \(1\) exactly for \(111,110,101,011\).
Check the martingale averages. Given \(X_1=0\), averaging the two possible \(M_2\) values gives \((0+\tfrac12)/2=\tfrac14=M_1\). Given \(X_1=1\), the average is \((\tfrac12+1)/2=\tfrac34=M_1\). Averaging \(M_1\) before any reveal gives \((\tfrac14+\tfrac34)/2=\tfrac12=M_0\). At the last reveal, for prefix \(00\) the terminal values are \(0,0\), with average \(0\); for \(01\) they are \(0,1\), with average \(\tfrac12\); for \(10\) they are \(0,1\), with average \(\tfrac12\); and for \(11\) they are \(1,1\), with average \(1\). Each average agrees with \(M_2\) for that prefix.
Worked Example: A Function with Pairwise Interactions
Let \(X_1,X_2,X_3\) be independent Bernoulli random variables with probabilities \(\mathbb{P}(X_1=1)=\tfrac13\), \(\mathbb{P}(X_2=1)=\tfrac12\), and \(\mathbb{P}(X_3=1)=\tfrac23\). Take \(f=X_1X_2+X_2X_3\), and reveal the coordinates in the order \(1,2,3\).
Before any reveal, independence gives \(\mathbb{E}f=(\tfrac13)(\tfrac12)+(\tfrac12)(\tfrac23)=\tfrac16+\tfrac13=\tfrac12\). After \(X_1=x_1\) is revealed, averaging the other coordinates gives \(M_1=\tfrac12x_1+\tfrac13\): the first product has mean \(x_1\mathbb{E}X_2=\tfrac12x_1\), and the second has mean \(\mathbb{E}X_2\,\mathbb{E}X_3=\tfrac13\). Thus \(M_1=\tfrac13\) if \(x_1=0\), and \(M_1=\tfrac56\) if \(x_1=1\).
After \(X_1=x_1\) and \(X_2=x_2\) are known, only \(X_3\) remains to be averaged, giving \(M_2=x_1x_2+\tfrac23x_2\). For prefixes \(00,01,10,11\), these values are respectively \(0,\tfrac23,0,\tfrac53\). Finally, \(M_3=X_1X_2+X_2X_3\). For the four triples \((x_1,x_2,0)\) and \((x_1,x_2,1)\), the terminal values are \(x_1x_2+x_2\cdot0\) and \(x_1x_2+x_2\), respectively.
Check the averages. Given \(X_1=0\), the two values of \(M_2\), for \(X_2=0\) and \(X_2=1\), are \(0\) and \(\tfrac23\); since \(X_2\) is fair, their average is \(\tfrac13=M_1\). Given \(X_1=1\), those values are \(0\) and \(\tfrac53\), with average \(\tfrac56=M_1\). Before revealing \(X_1\), the average of \(M_1\) is \((\tfrac23)(\tfrac13)+(\tfrac13)(\tfrac56)=\tfrac29+\tfrac5{18}=\tfrac12=M_0\). For the final step, if \(x_2=0\), both terminal values are \(0\), matching \(M_2=0\). If \(x_2=1\), averaging the terminal values \(x_1\) and \(x_1+1\) with probabilities \(\tfrac13\) and \(\tfrac23\) gives \(x_1+\tfrac23=M_2\). This checks the conditional average for every prefix.
Worked Example: The Order of Revelation Matters
Let \(X_1,X_2\) be independent Bernoulli random variables with success probabilities \(\tfrac13\) and \(\tfrac34\), respectively, on their product probability space. Let \(f=X_1X_2\), with a real-valued process indexed by \(k=0,1,2\). Compare the martingales obtained by revealing coordinate \(1\) first and coordinate \(2\) first.
The initial value is \(M_0=\mathbb{E}[X_1X_2]=(\tfrac13)(\tfrac34)=\tfrac14\). If \(X_1\) is revealed first, averaging over \(X_2\) gives \(M_1=\tfrac34X_1\), so its values for \(X_1=0,1\) are \(0,\tfrac34\). The terminal value is \(M_2=X_1X_2\).
Check the first conditional average: given \(X_1=0\), both possible terminal values are \(0\), with average \(0=M_1\). Given \(X_1=1\), the terminal values are \(0,1\), with probabilities \(\tfrac14,\tfrac34\); their mean is \((\tfrac14)0+(\tfrac34)1=\tfrac34=M_1\). Before the reveal, the mean of \(M_1\) is \((\tfrac23)0+(\tfrac13)(\tfrac34)=\tfrac14=M_0\).
If \(X_2\) is revealed first instead, averaging over \(X_1\) gives \(M_1=\tfrac13X_2\), with values \(0,\tfrac13\). Given \(X_2=0\), the terminal value is always \(0\). Given \(X_2=1\), the terminal value is \(X_1\), whose mean is \(0(\tfrac23)+1(\tfrac13)=\tfrac13=M_1\). The initial average is \((\tfrac14)0+(\tfrac34)(\tfrac13)=\tfrac14=M_0\). The order changes the intermediate conditional expectations, but both processes begin at \(\mathbb{E}f\) and end at \(f\).
What the Construction Does—and Does Not—Require
Each increment \(M_k-M_{k-1}\) is the change in the conditional estimate when coordinate \(k\) is revealed. The martingale property says that this change has conditional mean zero given the information available before that reveal. The intermediate values need not be the same for different reveal orders, as the third example shows. The endpoints remain the same: the unconditional mean and the fully observed function.
Common mistake: averaging as if dependent coordinates were independent. Let \(X_1\) be a fair Bernoulli variable and set \(X_2=X_1\). For \(f=X_2\), once \(X_1\) is revealed the true conditional expectation is \(\mathbb{E}[X_2\mid X_1]=X_1\), since \(X_2=X_1\). Incorrectly treating the unrevealed \(X_2\) as an independent fair coin gives \(\tfrac12\) for either value of \(X_1\). That calculation is wrong because the joint law is not the product of the marginal laws. The averaging formula in this tutorial relies on independence; for dependent coordinates, the conditional distribution of the unrevealed coordinates must account for what has already been observed.
Check Your Understanding
For each question, specify the information available at each stage and verify conditional averages using the distribution of the coordinates that remain.
- For two independent fair Bernoulli variables, take \(f=\mathbf{1}_{\{X_1+X_2=2\}}\). Find \(M_0,M_1,M_2\).
- For independent Bernoulli variables with success probabilities \(\tfrac14\) and \(\tfrac12\), take \(f=X_1+X_2\). Compute the martingale when \(X_1\) is revealed first.
- Why is integrability of \(f(X_1,\ldots,X_m)\) needed for the conditional-expectation construction?
- If two coordinates are dependent, which part of the unrevealed-coordinate averaging argument must be changed?
- In the pairwise-interaction example, compute \(M_1\) when \(X_1=0\) and verify it by averaging \(M_2\) over \(X_2\).