Following is from Csiszar and Shields' FnT monograph "Information Theory and Statistics":

The expectation–maximization or EM algorithm is an iterative method frequently used in statistics to estimate a distribution supposed to belong to a given set $\mathcal{Q}$ of distributions on a finite set $A$ when, instead of a "full" sample $x_1,\dots,x_n \in A^n$ from the unknown distribution, only an "incomplete" sample $y_1,\dots,y_n \in B^n$ is observable. Here $y_i = T(x_i)$ for a known mapping $T\colon A\to B$.

Can someone give a real time example of such a situation? What would be $T$ in such an example?


1 Answer 1


Consider a coin flipping experiment, where we are given two coins: A and B, with unknown probabilities of flipping Heads: $\theta_a$ and $\theta_b$. Our goal is to predict these $\theta$ values, i.e. a given set $Q$ of distributions, for each coin at the end of our experiment.

The experiment involves randomly picking either coin A or B, flipping it 10 times and recording all the results. It is depicted as below. Note that we know the identity of our coin in all five random coin picks. Going back to your question, this is the full data-set version.

enter image description here

Now, imagine we do the same thing as above but this time we do not know whether the coin that we randomly pick is A or B. There is a known mapping $T$ between the coin $id \in \{A, B\}$ -> $\theta_{id}$ which we cannot directly observe. So now we have incomplete data. The E-M solution for this is as depicted below. This is explained in the paper by Do and Batzoglou, so I won't go into more detail.

enter image description here

If you want to dig deeper, relevant code is provided in my previous answer here.

As a side note, the coin labels A and B have nothing to do with the $A$ and $B$ you define in your answer. This is potentially confusing, but I kept to them to be consistent with the figures from the paper.

  • $\begingroup$ Thank you. But, do you have an example situation exactly for the problem I have described? $\endgroup$
    – Kumara
    Jun 22, 2015 at 16:27
  • $\begingroup$ @Kumara, the example I gave is exactly the situation explained in your paragraph. I have slightly edited my answer to clarify. The first case where you can see the coin identities is the FULL version and is solvable by maximum likelihood. The second case, is the incomplete version where the coin identities are concealed, and we now have to use EM to learn the parameters. $\endgroup$
    – Zhubarb
    Jun 22, 2015 at 16:33
  • $\begingroup$ I think I need sometime to think over it. Thank you for spending your valuable time. $\endgroup$
    – Kumara
    Jun 22, 2015 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.