Detailed proof of the Law of the unconscious statistician

Question

Im trying to disentagle the proof of LOTUS but somehow got stuck in the last parts; this is the source on Quora which is pretty much the same as on Wikipedia.

Here's my attempt to do it in more detail:

• The definition of (discrete) Expectation is:

$\mathbb{E}_{P}[X] = \sum_{x \in \mathrm{\textit{Val}}(X)} \big( x \cdot P(X = x) \big)$

• $P(X)$ is a PMF, so a function that yields probability value for each value $x \in \mathrm{\textit{Val}}(X)$

• Step 1 (definition again)

$\mathbb{E}_{P}[Y] = \sum_{y \in \mathrm{\textit{Val}}(Y)} \big( y \cdot P(Y = y) \big)$

• Step 2: A function $g$ of a random variable, $Y = g(X)$

$\mathbb{E}_{P}[Y = g(X)] = \sum_{y \in \mathrm{\textit{Val}}(Y)} \big( y \cdot P(g(X) = y) \big)$

• Step 3: What to do with $P(g(X) = y)$?

$P(g(X) = y) = \sum_{x: g(x) = y; x \in \mathrm{\textit{Val}(X)}} P(X = x)$

• My understanding: OK, this is a transformation of $P(X)$ to $P(Y)$. It says, for any value of $y$ (for example "3"), find me all cases where $g(x)$ equals this $y$ (so it could be $g(0) = 3$ and $g(42) = 3$) and sum their probabilities (if $P(X = 0) = 0.12$ and $P(X = 42) = 0.01$ then $P(g(X) = 3) = 0.13$).

• Step 4: Plug it in

$\mathbb{E}_{P}[Y = g(X)] = \sum_{y \in \mathrm{\textit{Val}}(Y)} \big( y \cdot \sum_{x: g(x) = y; x \in \mathrm{\textit{Val}(X)}} P(X = x) \big)$

• Step 5: Move $y$ in the inner sum

$\mathbb{E}_{P}[Y = g(X)] = \sum_{y \in \mathrm{\textit{Val}}(Y)} \sum_{x: g(x) = y; x \in \mathrm{\textit{Val}(X)}} \big( y \cdot P(X = x) \big)$

• Step 6: Replace $y$ with $g(x)$

$\mathbb{E}_{P}[Y = g(X)] = \sum_{y \in \mathrm{\textit{Val}}(Y)} \sum_{x: g(x) = y; x \in \mathrm{\textit{Val}(X)}} \big( g(x) \cdot P(X = x) \big)$

• Step 7: Now what? The Quora answer says "But g(x) has to be something, so it is clear that this sum is just running over all possibilities for x" but I don't see it there.

Answer 1

Every value that $Y$ takes on is the result of applying $g(\cdot)$ to one or more values that $X$ takes on. In your own example, $Y=3$ is the value of $g(0)$ and $g(42)$ and no other values that $X$ might take on. That is, we can partition the set of all possible values that $X$ takes on into disjoint subsets (e.g. $\{0, 42\}$ maps to $Y=3$, $\{1,99\}$ maps to $Y=-\pi$, etc.) and so that last double sum in your question, when expanded out into an actual arithmetic expression with only $+$ signs with no mathematical gobbledygook like $\displaystyle \sum$ to distract us, can be seen to be just a re-arrangement of the sum $$g(0)P(X=0) + g(1)P(X=1) + \cdots + g(42)P(X=42) + \cdots + g(99)P(X=99) + \cdots $$ which, if we are so inclined, we can recombine into gobbledygook involving $\displaystyle \sum$ by writing $$E[Y] = E[g(X)] = \sum_i g(x_i)P(X=x_i)$$ which looks like LOTUS to me though ymmv.