3
$\begingroup$

I posted this question here Estimating Coin Flip Probabilities with Missing Information today.

Suppose there is a game where there are 2 Coins (Hidden Markov situation):

  • Coin 1 has a $p_1$ probability of landing on Heads and Coin 2 has a $p_2$ probability of landing on Heads
  • If Coin 1 is flipped, (regardless of the outcome) there is a $p_3$ probability of selecting Coin 1 to be flipped again. This means that there is a $1-p_3$ probability of selecting Coin 2 to be flipped if Coin 1 was selected in the previous turn.
  • If Coin 2 is flipped, (regardless of the outcome) there is a $p_4$ probability of selecting Coin 2 to be flipped again. This means that there is a $1-p_4$ probability of selecting Coin 1 to be flipped if Coin 2 was selected in the previous turn.

Suppose these coins are flipped $n$ times and we only have the results of the flips - we do not know if an individual result came from Coin 1 or Coin 2. However, we are told that there are 2 coins in this game, and that the probability of the coin being flipped depends on the previous coin that was flipped.

Our goal in this question is to estimate the probability of getting a heads in the next flip.

I wrote the likelihood for this question (i.e. likelihood for getting a heads in the next flip) as follows:

$$P(\text{Heads in Current Flip}) = P(\text{Heads in Coin 1}) \cdot P(\text{Selecting Coin 1 in Current Flip| Coin 1 was Selected in Previous Flip}) + P(\text{Heads in Coin 1}) \cdot P(\text{Selecting Coin 1 in Current Flip| Coin 2 was Selected in Previous Flip}) + P(\text{Heads in Coin 2}) \cdot P(\text{Selecting Coin 2 in Current Flip| Coin 1 was Selected in Previous Flip}) + P(\text{Heads in Coin 2}) \cdot P(\text{Selecting Coin 2 in Current Flip| Coin 2 was Selected in Previous Flip})$$

$$ L(X|C; p_1, p_2, p_3, p_4) = \prod_{i=1}^{n} P(X_i|C_i; p_1, p_2)P(C_i|C_{i-1}; p_3, p_4) $$

$$p_3 + p_4 = 1$$ $$0 \leq p_1, p_2, p_3, p_4 \leq 1$$

Now, I am trying to write the MLE equations to estimate $p_1, p_2, p_3, p_4$. As this is a Hidden Markov problem, I have read that it will require the use of the EM algorithm and the Forward-Backward algorithm. For me, this is intimidating as I have never used these techniques before - I will try to write my progress below.

Part 1: The way I see it, there are $i=2$ coins. Fundamentally, I think it would be useful to estimate the probability that at each "time point" (i.e. at each flip), what is the probability that Coin 1 was chosen and what was the probability that Coin 2 was chosen.

In this problem, the current state depends on the previous states - and the future states depend on the current state. Using the Backwards-Forwards Algorithm, we can write equations which calculate the probability of selecting Coin $i$ at time = $t$ given "everything" (i.e. previous coin selections and coin results) from time = 0 to time=$t$ (forward) .... and the probability of selecting Coin $i$ at time = $t$ given everything from the end to time= $t$ (backwards). (This took me some time to understand - initially I had thought that we are interesting in estimating from time=0 to some intermediate time=t, shouldn't we only use information from time=0 to t? Why are we using the full information from t=0 to time=max?. But I think now I understand that using the full information even at some intermediate time=t is still better than using information time=0 to t)

We can define $\alpha_{i}(t)$ as the probability of observing the partial sequence $X_1, X_2, ..., X_t$ and being in state $i$ at time $t$. We can also define $\beta_{i}(t)$ as the probability of observing the remaining sequence $X_{t+1}, X_{t+2}, ..., X_n$ given that we are in state $i$ at time $t$:

$$\alpha_{i}(t) = P(X_1, X_2, ..., X_t| C_t = i; p_1, p_2, p_3, p_4)$$ $$\beta_{i}(t) = P(X_{t+1}, X_{t+2}, ..., X_n | C_t = i; p_1, p_2, p_3, p_4)$$

Note that these formulas assume that we know the true values of $p_1, p_2, p_3, p_4$.

Part 2: Based on $\alpha_{i}(t)$ and $\beta_{i}(t)$, now we write equations to actually estimate what is the probability that Coin $i$ was actually selected at time =$t$ - these formulas are just simple ratio/proportions of observing an event vs all possible events that could be observed:

$$ \gamma_{i}(t) = \frac{\alpha_{i}(t)\beta_{i}(t)}{\sum_{j=1}^{2} \alpha_{j}(t)\beta_{j}(t)} $$

And $\xi_{i,j}(t)$ as the probability that Coin $i$ was flipped at time $t$ and Coin $j$ was flipped at time $t+1$:

$$ \xi_{i,j}(t) = \frac{\alpha_{i}(t) P(X_{t+1}|C_{t+1} = j; p_1, p_2) P(C_{t+1} = j|C_t = i; p_3, p_4) \beta_{j}(t+1)}{\sum_{k=1}^{2} \sum_{l=1}^{2} \alpha_{k}(t) P(X_{t+1}|C_{t+1} = l; p_1, p_2) P(C_{t+1} = l|C_t = k; p_3, p_4) \beta_{l}(t+1)} $$

Note that these formulas assume that we know the true values of $p_1, p_2, p_3, p_4$. And note that terms like $P(C_{t+1} = j|C_t = i; p_3, p_4)$ are basically the "old" estimates (i.e. at the $i-1^{th}$ iteration) that will come from the EM algorithm (upcoming parts).

Part 3: Two sets of formulas are needed to calculate $\alpha{i}(t)$ and $\xi_{i,j}(t)$ at all time points $t$. As I understand, this can be done by regular recursion formulas:

Forwards Step:

  1. Initialization: $\alpha_i(1) = P(X_1|C_1 = i; \theta_1)P(C_1 = i)$ for $i = 1, 2$.
  2. Recursion: $\alpha_i(t) = \left[\sum_{j=1}^{2} \alpha_j(t-1)P(C_t = i|C_{t-1} = j; \theta_2)\right] P(X_t|C_t = i; \theta_1)$ for $t = 2, ..., n$ and $i = 1, 2

Backwards Step:

  1. Initialization: $\beta_i(n) = 1$ for $i = 1, 2$.
  2. Recursion: $\beta_i(t) = \sum_{j=1}^{2} P(X_{t+1}|C_{t+1} = j; \theta_1)P(C_{t+1} = j|C_t = i; \theta_2)\beta_j(t+1)$ for $t = n-1, ..., 1$ and $i = 1, 2$.

Part 4: I think this is where the bulk of the EM algorithm comes in.

First, we can write the likelihood in terms of $\gamma_{i}(t)$ and $\xi_{i,j}(t)$:

$$ L(X, C; \theta) = \log P(X, C; \theta) = \sum_{t=1}^{n} \log P(X_t|C_t; p_1, p_2) + \log P(C_t|C_{t-1}; p_3, p_4) $$

$$ L(X, C; \theta) = \sum_{t=1}^{n} \sum_{i=1}^{2} \gamma_i(t) \log P(X_t|C_t=i; p_1, p_2) + \sum_{t=2}^{n} \sum_{i=1}^{2} \sum_{j=1}^{2} \xi_{ij}(t) \log P(C_t=j|C_{t-1}=i; p_3, p_4) $$

Then, we take the Expected Value (E-step) of the Likelihood. When evaluating the expectation, we replace the theoretical quantities in the likelihood with their data-based estimators (this also took me some time to understand why this replacement is allowed) in terms of $\gamma_i(t)$ and $\xi_{ij}(t)$ (note that $\theta = \{p_1, p_2, p_3, p_4\}$):

$$ Q(\theta, \theta^{(old)}) = E_{C|X, \theta^{(old)}}[L(X, C; \theta)] = \sum_{t=1}^{n} E_{C|X, \theta^{(old)}}[\log P(X_t|C_t; p_1, p_2)] + E_{C|X, \theta^{(old)}}[\log P(C_t|C_{t-1}; p_3, p_4)] $$

$$ Q(\theta, \theta^{(old)}) = \sum_{t=1}^{n} \sum_{i=1}^{2} \gamma_i(t) \log P(X_t|C_t=i; p_1, p_2) + \sum_{t=2}^{n} \sum_{i=1}^{2} \sum_{j=1}^{2} \xi_{ij}(t) \log P(C_t=j|C_{t-1}=i; p_3, p_4) $$

Then, we can maximize the E-step to get the following equations (e.g. for $p_1$, $p_2$):

  • Note that the term involving $p_1$ is $\gamma_1(t) \log P(X_t|C_t=1; p_1)$, which simplifies to $\gamma_1(t) \log p_1$ when $X_t = 1$ and $\gamma_1(t) \log (1 - p_1)$ when $X_t = 0$

$$ \frac{\partial Q(\theta, \theta^{(old)})}{\partial p_1} = \sum_{t=1}^{n-1} \frac{\gamma_1(t) X_t}{p_1} - \frac{\gamma_1(t) (1 - X_t)}{1 - p_1} $$

$$ \sum_{t=1}^{n-1} \gamma_1(t) X_t (1 - p_1) = \sum_{t=1}^{n-1} \gamma_1(t) p_1 (1 - X_t) $$

$$ \sum_{t=1}^{n-1} \gamma_1(t) X_t - \sum_{t=1}^{n-1} \gamma_1(t) X_t p_1 = \sum_{t=1}^{n-1} \gamma_1(t) p_1 - \sum_{t=1}^{n-1} \gamma_1(t) X_t p_1 $$

$$ \sum_{t=1}^{n-1} \gamma_1(t) X_t = \sum_{t=1}^{n-1} \gamma_1(t) p_1 $$

$$ p_1^{(new)} = \frac{\sum_{t=1}^{n-1} \gamma_1(t) X_t}{\sum_{t=1}^{n-1} \gamma_1(t)} $$

Using the same logic, we can obtain:

$$ p_2^{(new)} = \frac{\sum_{t=1}^{n-1} \gamma_2(t) X_t}{\sum_{t=1}^{n-1} \gamma_2(t)} $$

And for $p_3$ (and $p_4$), we can do:

$$ \frac{\partial Q(\theta, \theta^{(old)})}{\partial p_3} = \sum_{t=1}^{n-1} \frac{\xi_{1,1}(t)}{p_3} - \frac{\gamma_1(t) - \xi_{1,1}(t)}{1 - p_3} $$

$$ \sum_{t=1}^{n-1} \frac{\xi_{1,1}(t)}{p_3} - \frac{\gamma_1(t) - \xi_{1,1}(t)}{1 - p_3} = 0 $$

$$ \sum_{t=1}^{n-1} \xi_{1,1}(t) - \sum_{t=1}^{n-1} \xi_{1,1}(t) p_3 = \sum_{t=1}^{n-1} \gamma_1(t) p_3 - \sum_{t=1}^{n-1} \xi_{1,1}(t) p_3 $$

$$ p_3^{(new)} = \frac{\sum_{t=1}^{n-1} \xi_{1,1}(t)}{\sum_{t=1}^{n-1} \gamma_1(t)} $$

Using the same logic, we can obtain:

$$ p_4^{(new)} = \frac{\sum_{t=1}^{n-1} \xi_{2,2}(t)}{\sum_{t=1}^{n-1} \gamma_2(t)} $$

Remember that at the end of an iteration, $p_3^{(new)}$ and $p_4^{(new)}$ will be used in the $\xi_{i,j}(t)$ formulas , i.e. for the $P(C_{t+1} = j|C_t = i; p_3, p_4)$

Conclusion:

  • (Although I seriously doubt it and likely made many mistakes) Is my analysis correct?
  • I am still not sure how to add the constraints to these estimating equations and how to calculate the variances of the parameter estimates (other than using a bootstrap like procedure).
$\endgroup$
3
  • 2
    $\begingroup$ Your question appears to be "Is my analysis correct?" But because your analysis is so prolonged, you are asking far too much of users of this site, especially because you have offered little or nothing to motivate the question or make it of general interest. Thus, if you could (a) simplify the situation and its analysis and (b) explain why we might want to think about it, you would stand a better chance of getting thoughtful replies. $\endgroup$
    – whuber
    Jan 21 at 14:36
  • $\begingroup$ thanks for the feedback ... I will try to shorten it next time ... I just wanted to show all my steps . I am always paranoid that I am misunderstanding something, taking the derivatives incorrectly, taking the expected value incorrectly, etc... $\endgroup$ Jan 21 at 16:30
  • $\begingroup$ I took the advice that I was given in my previous question (stats.stackexchange.com/questions/636389/…) and narrowed it down to a single question (as I did here) $\endgroup$ Jan 21 at 16:34

1 Answer 1

1
$\begingroup$

The problem has unobserved nuisance parameters $C_i$. The probability of these $C_i$ are themselves depending on the parameters and you can compute the likelihood by summing over all $2^n$ possibilities

$$P(\vec{X}|p_1,p_2,p_3,p_4) = \sum_{\forall \vec{C}} P(\vec{X}, \vec{C}|p_1,p_2,p_3,p_4) = \sum_{\forall \vec{C}} P(\vec{X}, |\vec{C},p_1,p_2) P(\vec{C}|p_3,p_4) $$

and this will be a sum a polynomial with terms $p_1$, $p_2$, $p_3$ and $p_4$.


If you want to compute this polynomial in an itterative fashion then you can consider joint probabilities for the vector of size $n$ and the last state (there are two for $s=1$ and $s=2$)

$$P(\vec{X}_n,C_n=s|p_1,p_2,p_3,p_4)$$

and use those to compute probabilities for the vector of size $n+1$ and the last state

$$P(\vec{X}_{n+1},C_{n+1}=s|p_1,p_2,p_3,p_4)$$

Let's for simplicity write $P(n,s)$ for these probabilities then:

$$P(n+1,1) = \left( P(n,1) p_3 + P(n,2) (1-p_4) \right) \left(p_1^{X_{n+1}} (1-p_1)^{1-X_{n+1}} \right)\\ P(n+1,2) = \left( P(n,1) (1-p_3) + P(n,2) p_4 \right) \left(p_2^{X_{n+1}} (1-p_2)^{1-X_{n+1}} \right)\\$$

$\endgroup$
1
  • $\begingroup$ thanks for your efforts ... i am trying to digest... would you say that the (long and inefficient) work I have shown is equivalent to the work you have done for this problem? $\endgroup$ Jan 23 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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