User:IssaRice/Belief propagation two coins and a bell example

This is an example that illustrates belief propagation in a simple polytree. The situation is given by Pearl (though he doesn't use it as an example of belief propagation). There are two coins, left and right, and a bell. The bell rings when the two coins land on the same side.

We can draw a Bayesian network like this: $L\rightarrow B\leftarrow R$, where $L$ is a random variable representing the left coin flip, $B$ the bell, and $R$ the right coin flip.

Initially, ${\mathit {BEL}}(L)={\mathit {BEL}}(B)={\mathit {BEL}}(R)=(1/2,1/2)$ because each variable has two possible states with equal probabilities between them.

Now what happens when we learn that the left coin came up heads? We can draw an evidence node going into L: $e_{L}^{+}\rightarrow L\rightarrow B\leftarrow R$.

The L node now recalculates:

• $\pi (L)=P(L\mid e_{L}^{+})=(1,0)$
• ${\mathit {BEL}}(L)=\alpha (1,1)(1,0)=(1,0)$

It then sends the message $\pi _{B}(L)=P(L\mid e_{LB}^{+})=(1,0)$ to B.

B calculates:

${\begin{aligned}\pi (B)=P(B\mid e_{B}^{+})&=\sum _{(i,j)\in \{h,t\}^{2}}P(B\mid L=i,R=j)P(L=i,R=j\mid e_{LB}^{+})\\&=\sum _{(i,j)\in \{h,t\}^{2}}P(B\mid L=i,R=j)P(L=i\mid e_{LB}^{+})P(R=j)\\&=(1,0)\cdot 1\cdot 1/2+(0,1)\cdot 1\cdot 1/2+(0,1)\cdot 0\cdot 1/2+(1,0)\cdot 0\cdot 1/2\\&=(1/2,1/2)\end{aligned}}$

This makes sense: the two coin flips are independent, so knowing just L shouldn't change your probability that the bell rang.

As a side note, Pearl writes the summation like this:

$\sum _{u_{1},\ldots ,u_{n}}P(x\mid u_{1},\ldots ,u_{n})P(u_{1}\mid e_{U_{1}X}^{+})\cdots P(u_{n}\mid e_{U_{n}X}^{+})$

but this is pretty confusing since in the above, the $u_{j}$s are all specific values whereas the x is an abstract value.