The distribution of the composition of two random functions

44 Views Asked by At

Let $A$ and $B$ be two random functions of binary variables (e.g., two probabilistic algorithms). Then, on input $x \in \{0,1\}^*$, $A(x)$ outputs $y \in \{0,1\}^{f_A(|x|)}$ with probability $p_A(A(x) = y)$ for some (e.g. polynomial) function $f_A : \mathbb{N} \rightarrow \mathbb{N}$. Similarly for $B$.

I am interested in what the distribution of $B(A(x))$ is for different inputs $x$. My gut tells me that $$ p_{B \circ A}(B(A(x)) = y) = \sum_{z \in \{0,1\}^{f_A(|x|)}} p_A(A(x) = z)p_B(B(z) = y), $$ however I'm not sure how to formally prove this.