6
$\begingroup$

I am trying to create an example that shows how the quality of estimation is impacted by incomplete information (e.g. deliberately neglecting the Markov Property) and wrong assumptions about the data generating process (original question: How do Incorrect Statistical Assumptions affect Estimation?).

Here is an example I came up with.

Suppose there is a game where there are 2 Coins and 2 Players (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.

Now, suppose these coins are flipped $n$ times and both players only have the results of the flips - they do not know if an individual result came from Coin 1 or Coin 2

  • Player 1 is told that there is only 1 coin in this game
  • Player 2 is 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

Suppose the real values of $p_1, p_2, p_3, p_4$ are unknown to both players. Both players are tasked with estimating the general probability of getting a heads in the next turn, and the variance of this estimator (this allows both players to have a common metric that they will both estimate, allowing for comparison). Which player will have the advantage (i.e. have closer estimates to the true values) in this game - and by how much??

Here is what I tried so far:

  • Player 1:

Player 1 will treat each flip as a Bernoulli trial and treat the collection of $n$ flips as a Binomial problem. Presented with $n$ coin flips $X = x_1, x_2, ..., x_n$, we know that:

$$E(X) = \hat{\mu} = np$$ $$Var(X) = np(1-p)$$ $$Var(\hat{\mu}) = \frac{Var(X)}{n} = p(1-p)$$

Since Player 1 only believes there is 1 coin, the probability of getting a heads in this game can be estimated from Maximum Likelihood Estimation:

$$L(p; x) = \prod_{i=1}^n p^{x_i}(1-p)^{1-x_i} = p^{\sum_1^n x_i}(1-p)^{\sum_1^n1-x_i} = p^{x}(1-p)^{n-x}$$

$$\log L(p; x) = x \log p + (n - x) \log (1 - p)$$

$$\frac{d}{dp} \log L(p; x) = \frac{x}{p} - \frac{n - x}{1 - p}$$

$$0 = \frac{x}{p} - \frac{n - x}{1 - p}$$

$$\hat{p}_{\text{MLE}} = \frac{x}{n}$$

And the Variance can be calculated as $Var(\hat{p}_{\text{MLE}})$ is :

$$Var(\hat{p}_{\text{MLE}}) = \frac{np(1-p}{n} = p(1-p) $$

  • Player 2:

Player 2 is a more complicated case since there are several ways in which a Heads can be obtained. In any given flip, the result of the current flip depends on the previous flip.

The general probability of Heads in the next flip is:

$$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})$$

Mathematically, if we define a sequence of coin flips as $X = \{X_1, X_2, ..., X_n\}$, where $X_i$ is the result of the $i$-th flip (1 for heads, 0 for tails), the sequence of coin selections as $C = \{C_1, C_2, ..., C_n\}$, where $C_i$ is the coin selected in the $i$-th turn (1 for Coin 1, 2 for Coin 2)

$$ 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(X_i|C_i; p_1, p_2) = \begin{cases} p_1^{X_i}(1-p_1)^{1-X_i} & \text{if } C_i = 1 \\ p_2^{X_i}(1-p_2)^{1-X_i} & \text{if } C_i = 2 \end{cases} $$

$$ P(C_i|C_{i-1}; p_3, p_4) = \begin{cases} p_3 & \text{if } C_{i-1} = 1 \text{ and } C_i = 1 \\ 1-p_3 & \text{if } C_{i-1} = 1 \text{ and } C_i = 2 \\ p_4 & \text{if } C_{i-1} = 2 \text{ and } C_i = 2 \\ 1-p_4 & \text{if } C_{i-1} = 2 \text{ and } C_i = 1 \end{cases} $$

Using indicator variables $I_{1i}$ and $I_{2i}$ to represent if a given $X_i$ came from Coin 1 or Coin 2:

$$ I_{1i} = \begin{cases} 1 & \text{if } C_i = 1 \\ 0 & \text{otherwise} \end{cases} $$

$$ I_{2i} = \begin{cases} 1 & \text{if } C_i = 2 \\ 0 & \text{otherwise} \end{cases} $$

We can write the Likelihood for Player 2 as:

$$ L(X|C; p_1, p_2, p_3, p_4) = \prod_{i=1}^{n} \left[p_1^{X_i I_{1i}}(1-p_1)^{(1-X_i) I_{1i}}p_2^{X_i I_{2i}}(1-p_2)^{(1-X_i) I_{2i}}\right] \times \left[p_3^{I_{1i}I_{1,i-1}}(1-p_3)^{I_{2i}I_{1,i-1}}p_4^{I_{2i}I_{2,i-1}}(1-p_4)^{I_{1i}I_{2,i-1}}\right] $$

Thus, for some:

  • Observed data $x_1,x_2, ... x_n$
  • Where $n_{H1}$ number of heads from Coin 1 , $n_{T1}$ number of tails from Coin 1, $n_{H2}$ number of heads from Coin 2, $n_{T2}$ number of tails from Coin 2
  • And $n_{11}$ is the number of times Coin 1 was chosen after Coin 1 , $n_{12}$ is the number of times Coin 2 was chosen after Coin 1, $n_{21}$ is the number of times Coin 1 was chosen after Coin 2, $n_{22}$ is the number of times Coin 2 was chosen after Coin 2

We can write the Likelihood and Log-Likelihood as:

$$ L(p_1, p_2, p_3, p_4, n_{H1}, n_{T1}, n_{H2}, n_{T2}, n_{11}, n_{12}, n_{21} , n_{22}) = p_1^{n_{H1}}(1-p_1)^{n_{T1}}p_2^{n_{H2}}(1-p_2)^{n_{T2}}p_3^{n_{11}}(1-p_3)^{n_{12}}p_4^{n_{22}}(1-p_4)^{n_{21}} $$

$$ \ln L = n_{H1}\ln p_1 + n_{T1}\ln(1-p_1) + n_{H2}\ln p_2 + n_{T2}\ln(1-p_2) + n_{11}\ln p_3 + n_{12}\ln(1-p_3) + n_{22}\ln p_4 + n_{21}\ln(1-p_4) $$

Where:

  • $n_{H1} = \sum_{i=1}^{n} X_i I_{1i}$
  • $n_{H2} = \sum_{i=1}^{n} X_i I_{2i}$
  • $n_{T1} = \sum_{i=1}^{n} (1 - X_i) I_{1i}$
  • $n_{T2} = \sum_{i=1}^{n} (1 - X_i) I_{2i}$
  • $n_{11} = \sum_{i=1}^{n} I_{1i}I_{1,i-1}$
  • $n_{12} = \sum_{i=1}^{n} I_{2i}I_{1,i-1}$
  • $n_{21} = \sum_{i=1}^{n} I_{1i}I_{2,i-1}$
  • $n_{22} = \sum_{i=1}^{n} I_{2i}I_{2,i-1}$

With constraints: $$p_3 + p_4 = 1$$ $$0 \leq p_1, p_2, p_3, p_4 \leq 1$$ $$\sum (n_{H1} + n_{H2} + n_{T1} + n_{T2}) = n$$ $$\sum (n_{11} + n_{12} + n_{21} + n_{22}) = n$$ $$ n_{11} + n_{21} = n_{H1} + n_{T1}$$ $$ n_{22} + n_{12} = n_{H2} + n_{T2}$$

Here is where I got stuck: The above system is quite complicated to solve (my own attempt to solve it here Estimating Coin Flip Probabilities with Missing Information) and would like require numerical optimization algorithms (https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm).

Furthermore, I am not sure how to then calculate $Var(\hat{p}_{1_{\text{MLE}}})$, $Var(\hat{p}_{2_{\text{MLE}}})$, $Var(\hat{p}_{3_{\text{MLE}}})$, $Var(\hat{p}_{4_{\text{MLE}}})$. I saw some links on this Variance of EM mean estimates in a simple mixture of two normals, but I don't understand why this is a valid procedure and how to implement it in R.

I was thinking of trying to write some R code to perform simulations. For example:

  • Step 1: Fix values of $p_1, p_2, p_3, p_4$
  • Step 2: Simulate $n$ random coin flips
  • Step 3: Estimate the general probability of heads using basic MLE for Player 1 and using the EM algorithm of heads for Player 2. (repeat this for variance estimates as well)
  • Step 4: Repeat Step 2 and Step 3 many times - compare how far Player 1 and Player 2 deviate from the true values
  • Step 5 (Optional): Pick new values of $p_1, p_2, p_3, p_4$ and repeat Step 2 - Step 4

But is there a more a "theoretical" way to analyze this question (i.e. comparing quality of estimates under full information vs incomplete information) instead of using simulations (i.e. for any number of coins, any number of flips, any probability values)? Can we theoretically analyze the advantage of Player 2 in this game (and then validate this through simulation)?

  • Note: I wonder what would happen if there was a 3rd Player who was told that there are actually 3 coins in this game...would Player 3's estimates of the general heads probability be worse than Player 2 but similar to Player 1?
$\endgroup$
16
  • $\begingroup$ A minor comment: the variance of the estimator is not (by itself) a good measure. I would just say $\hat p = 0.5$ and be done with it. (: Are you restricting yourself to unbiased estimates? Or perhaps you want to compare the MSE of the two approaches. $\endgroup$
    – knrumsey
    Commented Jan 20 at 23:28
  • $\begingroup$ these are all good points that I had not thought about.... thanks $\endgroup$ Commented Jan 21 at 2:22
  • 2
    $\begingroup$ This is an interesting problem, and I'll think about it more if I have time... But I think the situation for player 2 is more difficult than you're making it out to be. In a usual sequence of coin flips, the probability of a sequence is unaffected by the order (HHHT is the same as HTHH), and so we can "weight" the resulting probability appropriately using binomial coefficients. In this setting though, the ordering of the sequence directly affects the probability. In short, I think your likelihood for player 2 is incorrect. $\endgroup$
    – knrumsey
    Commented Jan 21 at 4:53
  • $\begingroup$ All is not lost however, this problem might be (should be?) solvable using Markov chains. $\endgroup$
    – knrumsey
    Commented Jan 21 at 4:54
  • 2
    $\begingroup$ You could save a lot of space and probably attract more attention if you shortened this by, for example, not bothering to write out the equations stating that each derivative equals zero at the optimum. Other opportunities abound! $\endgroup$
    – jbowman
    Commented Jan 21 at 17:36

0

Your Answer

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

Browse other questions tagged or ask your own question.