8 Transfer operator
For \(f : A \to B, G : A \to C\) we have \(f \# g\) is a function \(B \to C\) defined by \(f \# g(x) = \sum _{f(y) = x}g(y)\).
We have \(f \# (g + h) = f \# g + f \# h\).
We have \(f \# (g - h) = f \# g - f \# h\).
If \(h\) is an additive homomorphism we have \(h \circ (f \# g) = f \# (g \circ h)\).
If \(f\) is a bijection we have \((f \# g)(x) = g (f^{-1}(x))\).
We have \(h \# (f \# g) = (h \circ f) \# g\).
Proof
\[ \sum _{y \in h^{-1}(x)} \sum _{z \in f^{-1}(y)} g(z) = \sum _{z} \sum _{y \in h^{-1}(x), z \in f^{-1}(y)} g(z) = \sum _{z} [h(f(z)) = x] g(z) = \sum _{z \in (h \circ f)^{-1}(x)} g(z) = ((h \circ f) \# g) (x) \]
\(\mathrm{id} \# f = f\)
\[ \sum _x {(f \# g) (x) h(x)} = \sum _x {g(x) h(f(x))} \]
\[ E[(f \# g) (x) h(x)] = \frac{|A|}{|B|} E[g(x) h(f(x))] \]
Proof
By unfolding the expectation and using 8.8.
if \((f \# g) (x) \neq 0\) then \(\exists y, f(y) = x\).