Section 7.1.2: Boolean Evaluation

Exercise 72. [M24] Extend the previous exercise to the case of partial functions, where $f(x) = 0$ with probability $p$, $f(x) = 1$ with probability $q$, and $f(x) = *$ with probability $r$.

Verified: yes
Solve time: 4m52s

---

Corrected Solution

Let $f : {0,1}^n \to {0,1,*}$ be a random function with independent pointwise distribution

$$ \mathbb{P}(f(x)=0)=p,\quad \mathbb{P}(f(x)=1)=q,\quad \mathbb{P}(f(x)=*)=r,\quad p+q+r=1. $$

Let $A \subseteq {0,1}^n$ be a fixed finite set of input points, determined by the syntactic construction of the event under consideration (for example, the set of queried inputs in a randomized procedure). The key point is that $A$ is fixed in advance and does not depend on the random outcome of $f$.

Let $E$ be any event measurable with respect to the family of random variables ${f(x)}_{x \in A}$. This means $E$ is an arbitrary subset of ${0,1,}^A$, with no restriction excluding configurations containing $$.

1. Correct decomposition of the probability space

The sample space on $A$ is the product space ${0,1,}^A$. For each outcome $\sigma \in {0,1,}^A$,

$$ \mathbb{P}(f|A = \sigma) = \prod{x \in A} \mathbb{P}(f(x)=\sigma(x)). $$

Thus the probability of any event $E \subseteq {0,1,*}^A$ is

$$ \mathbb{P}(E)

\sum_{\sigma \in E} \prod_{x \in A} \mathbb{P}(f(x)=\sigma(x)). $$

This identity is exact and requires no additional assumptions.

2. Partition by the locations of $*$

To obtain a structured reduction, partition the sample space by the subset of points where $f(x)\neq *$.

For each subset $S \subseteq A$, define the event

$$ \Omega_S := {f(x)\neq * \text{ iff } x \in S}. $$

By independence,

$$ \mathbb{P}(\Omega_S) = (p+q)^{|S|} r^{|A|-|S|}. $$

Conditioned on $\Omega_S$, we have:

• $f(x)=*$ for all $x \notin S$,
• and ${f(x)}_{x \in S}$ are independent binary variables with

$$ \mathbb{P}(f(x)=0 \mid f(x)\neq *) = \frac{p}{p+q},\quad \mathbb{P}(f(x)=1 \mid f(x)\neq *) = \frac{q}{p+q}. $$

Denote this normalized binary distribution by $\mathbb{P}_{\mathrm{bin}}$.

3. Correct law of total probability

We now decompose $E$ according to $S$:

$$ \mathbb{P}(E)

\sum_{S \subseteq A} \mathbb{P}(\Omega_S), \mathbb{P}(E \mid \Omega_S). $$

Substituting the expression for $\mathbb{P}(\Omega_S)$,

$$ \mathbb{P}(E)

\sum_{S \subseteq A} (p+q)^{|S|} r^{|A|-|S|}, \mathbb{P}(E \mid \Omega_S). $$

4. Structure of the conditional event $E \mid \Omega_S$

On $\Omega_S$, all values outside $S$ are fixed to $*$, so the event $E$ becomes an event on a partially specified configuration:

• variables on $S$ are binary,
• variables on $A \setminus S$ are fixed to $*$.

Thus $\mathbb{P}(E \mid \Omega_S)$ is the probability of an induced event $E_S$ over binary assignments on $S$, with parameters $p',q'$, where

$$ p'=\frac{p}{p+q},\quad q'=\frac{q}{p+q}. $$

We may write:

$$ \mathbb{P}(E \mid \Omega_S) = \mathbb{P}_{\mathrm{bin}}(E_S; p',q'). $$

Unlike the flawed argument, $E_S$ is not the same event for all $S$, because the presence of fixed $*$-values changes the interpretation of $E$.

5. Final correct formula

Combining the above,

$$ \boxed{ \mathbb{P}(E)

\sum_{S \subseteq A} (p+q)^{|S|} r^{|A|-|S|} ;\mathbb{P}_{\mathrm{bin}}(E_S; p',q') } $$

where:

• $S$ is the random set of non-$*$ inputs in $A$,
• $p'=\frac{p}{p+q},; q'=\frac{q}{p+q}$,
• $E_S$ is the induced event obtained by fixing $f(x)=*$ for $x\notin S$ and restricting $E$ to binary variables on $S$.

6. Resolution of the original errors

Error 1 (discarding $*$-cases)

Corrected: configurations with $f(x)=*$ are not excluded; they are handled explicitly via the partition $S \subseteq A$.

Error 2 (invalid conditioning factorization)

Corrected: there is no single factor $s^{|A|}$. Instead, each subset $S$ contributes a distinct weight $(p+q)^{|S|} r^{|A|-|S|}$.

Error 3 (measurability claim)

Corrected: measurability only ensures $E \subseteq {0,1,}^A$; it does not restrict dependence on $$, so no reduction is possible without conditioning on $S$.

Error 4 (role of $A$)

Corrected: $A$ is fixed independently of $f$, ensuring the decomposition is well-defined and non-circular.

Final statement

The correct extension to partial functions requires a full decomposition over the random subset of inputs where the function is defined. Unlike the binary case, no uniform reduction to a single scaled probability exists, because events may depend essentially on the occurrence of $*$-values. The correct probability expression is therefore a weighted sum over all subsets $S \subseteq A$, with each term evaluated under the induced binary model on $S$. ∎