Expectation Maximization Clarification I found very helpful tutorial regarding EM algorithm.
The example and the picture from the tutorial is simply brilliant.

Related question about calculating probabilities how does expectation maximization work?
I have another question regarding how to connect the theory described in tutorial to the example. 

During the E-step, EM chooses a function $g_t$ that lower bounds $\log P(x;\Theta)$ everywhere, and for which $g_t( \hat{\Theta}^{(t)}) = \log P(x; \hat{\Theta}^{(t)})$.

So what the $g_t$ in our example, and it looks like it should be different for every iteration.
In addition, in example $\hat{\Theta}_A^{(0)} = 0.6$ and $\hat{\Theta}_B^{(0)} = 0.5$ then applying them to the data we get that $\hat{\Theta}_A^{(1)} = 0.71$ and $\hat{\Theta}_B^{(1)} = 0.58$. Which is for me looks counter intuitive. We had some prior assumptions, applied it to the data and get new assumptions, so the data somehow changed the assumptions. I don't understand why $\hat{\Theta}^{(0)}$ doesn't equal to $\hat{\Theta}^{(1)}$.
In addition, more questions emerge when you see Supplementary Note 1 to this tutorial. For example what is $Q(z)$ in our case. It's not clear to me why the inequality is tight when $Q(z)=P(z|x;\Theta)$
Thank you.
 A: I found these notes very helpful in figuring out what was going on in the supplemental material.
I'll answer these questions a bit out of order for continuity.

First: why is it that 
$\theta^{(0)} \ne \theta^{(1)}$
The reason is that the our function $g_0$ is chosen such that it is guaranteed to be less than or equal to $\log(P(x;\theta))$, with the 2 being incident at the point of our initial guess $\theta^{(0)}$. If our prior assumptions were perfect initial guesses then you would be correct and $\theta^{(1)}$ would be unchanged. But we can find higher values in the created function $g_0$, so our next iteration of the parameter for $\theta$ is guaranteed to be more likely than our original.

Second: why is the inequality tight when 
$$ Q(z) = P(z|x;\theta) $$
There is a hint in the footnotes about this where it says,

equality holds if and only if the random variable is constant with
  probability 1 (i.e., $y=E[y]$)

implying that our choice of $Q$ makes $\frac{P(x, z; \theta)}{Q(z)}$ constant. To see this, consider that:
$$ P(x, z ; \theta) = P(z | x; \theta) P(x; \theta) $$ 
which makes our fraction
$$ \frac{P(z | x; \theta) P(x; \theta)}{P(z|x;\theta)}  = P(x; \theta)$$
So what is $P(x; \theta)$ and is it constant? Well, consider that we are calculating the sums over $z$ for which this term is independent (constant). Let's represent it as $C$ and that equation becomes:
$$ \log{\big( \sum_z{Q(z)C} \big)} \ge \sum_z{Q(z)\log(C)} $$
from here we can see pretty quickly that the 2 sides are equal, as the expectation of a constant will be that constant no matter the weights (the $Q(z)$)

Lastly: what is $g_t$
The answer given in the notes I linked is slightly different from the one in the supplementary notes, but they differ only by a constant and we are maximizing it so it is not of consequence. The one in the notes (with derivation) is:
$$ g_t(\theta) = \log(P(x|\theta^{(t)})) + \sum_z{P(z|x;\theta^{(t)})\log{\big( \frac{P(x|z;\theta)P(z|\theta)}{P(z|x;\theta^{(t)})P(x|\theta^{(t)})} \big)}} $$
This complex formula isn't talked about at length in the supplementary notes, probably because a lot of these terms will be constants that get thrown away when we maximize. If you are interested in how we arrive here in the first place, I recommend those notes I linked.
Using a similar argument to the one made in the answer to the second question, the term in the log is equal to 1 for $g_t(\theta^{(t)})$ so the sum term goes away and $g_t(\theta^{(t)}) = \log P(x|\theta^{(t)})$ as expected.
A: The following questions extracted from your question once also challenged me:  

So what the $g_t$ in our example, and it looks like it should be different for every iteration.

Firstly the $\log P(X; \hat{\theta})=\log \sum_z p(z, X; \hat \theta)=\log \sum_z Q(z) \frac{p(z, X; \hat \theta)}{Q(z)}$ and the $g_t$ function is $\sum_z Q(z) \log  \frac{p(z, X; \hat \theta)}{Q(z)}$, and the following inequality holds due to the concavity of $\log$ and the Jensen's inequality: 
$$\log \sum_z Q(z) \frac{p(z, X; \hat \theta)}{Q(z)} \geq \sum_z Q(z) \log  \frac{p(z, X; \hat \theta)}{Q(z)}=g_t$$ 
Yes, $g_t$ is different for each iteration, and it is the green curves in the following figure from the Supplementary Note 1: 


In addition, in example $\hat{\Theta}_A^{(0)} = 0.6$ and $\hat{\Theta}_B^{(0)} = 0.5$ then applying them to the data we get that $\hat{\Theta}_A^{(1)} = 0.71$ and $\hat{\Theta}_B^{(1)} = 0.58$. Which is for me looks counter intuitive.

If we treat $\hat{\Theta}^{(0)}$, representing $\hat{\Theta}_A^{(0)}$ and $\hat{\Theta}_B^{(0)}$, as $\theta^{(t)}$ in the above figure, $\hat{\Theta}^{(1)}$ can be treated as $\theta^{(t+1)}$ which more approximates the ground truth(the 0.8 and 0.45 we get in part (a) Maximum likelihood estimation with complete data).

I don't understand why $\hat{\Theta}^{(0)}$ doesn't equal to $\hat{\Theta}^{(1)}$.

Once we have fixed/hallucinated $z$ the lower bound function is also fixed as anyone of the green curves in the above figure(for instance $g_t$ in the above figure), and we can calculate the maximum likelihood like we do we have no missing data by choosing the $\hat{\Theta}^{(1)}$ or the $\theta^{(t+1)}$ in the figure(treating $\hat{\Theta}^{(0)}$ as $\theta^{(t)}$). They are not equal because $\theta^{(t)}$ is not the maximum of the lower bound $g_t$, but $\theta^{(t+1)}$ is. 
Actually we optimize $\theta$ in each step to approximate the ground truth(0.8 and 0.45 in our case). 

For example what is $Q(z)$ in our case. It's not clear to me why the inequality is tight when $Q(z)=P(z|x;\Theta)$

This is really a good question. $z$ stands for either coin A or coin B, and $Q(z)$ is for how confident the coin is A or B: $Q_i(z^{(i)}=A)$ for each observation i. $Q(z)$ is a distribution of $z$ and it sums up to 1: $\sum_z Q_i(z^{(i)})=1$. 
Let's go back to the Jensen't inequality:  
$$\log \sum_z Q(z) \frac{p(z, X; \hat \theta)}{Q(z)} \geq \sum_z Q(z) \log  \frac{p(z, X; \hat \theta)}{Q(z)}$$
The equality only hold when $\frac{p(z, X; \hat \theta)}{Q(z)}$ is constant(please refer to this answer) since $\log (x)$ is not affine, then $\frac{p(z, X; \hat \theta)}{Q(z)}=C$ or $Q(z)\propto p(z, X; \hat \theta)$. To make $Q(z)$ a distribution, as we stated earlier, we can get the following: 
\begin{align}
Q(z) &\overset{\text{like normalization}}{=} \frac{p(z, X; \hat \theta)}{\sum_z p(z, X; \hat \theta)} \\
&= \frac{p(z, X; \hat \theta)}{p(X; \hat \theta)}\\
&= p(z|X,\hat \theta)
\end{align}
This tutorial: The EM algorithm by Andrew Ng helped me a lot and so did this one: The expectation maximization algorithm: A short tutorial. 
Hope that helps, and if you have any more questions please update me. 
