# How to untangle multiple, mixed Bernoulii distributions

In my universe there are a infinite number of opaque boxes that are either:

• empty
• has a red marble
• has a blue marble
• has both a red and a blue marble

p(r) gives probability that there is a red marble in the box p(b) gives probability that there is a blue marble in the box

These probabilities are independent. In addition, I have two keys, K(r) (red key), and K(b), (blue key). A key of a given color may open the box ONLY if marble of that color is in the box. What is tricky is that keys are not reliable at opening the boxes, on a given attempt

• p(Kr) gives the probability that red key will open the box if red marble present
• p(Kb) gives the probability that blue key will open the box if blue marble present
• when a box is opened w/ either red or blue key we CAN NOT tell if the other color marble is present (meaning the other key also would have eventually worked); ability to learn about presence or absence of other color marble is lost once the box is opened.

Again, these key probabilities are independent. My universe is constructed from these 4 probabilities p(r), p(b), p(Kr), p(Kb) but I don't know these values. These are the values that I am trying to determine by repeatedly trying my 2 keys on (infinite) supply of boxes that I do have. My strategy:

• Pick a box
• repeatedly try red/blue keys randomly till either the box opens and I record which color key opened it.
• give up after 20 (or some other number) of attempts and pick a new box
• if successful or not I would have full record of exact sequence of keys that I have attempted

Based on a large number of observations I would like to know if I can correctly determine my 4 probability values.

I wrote a simulation and attempted a few things. When I have a success I count the number of failed key attempts of the successful key before its success. This gives an estimate of P(Kx) (where x is r or b), but estimates seem biased and tend to be too high. This is I believe because I discard information regarding failed attempts w/ the other key before a given key does succeed. But I don't know how to use the information regarding failures.

Any hints welcome, I have tried to read up on "bernoulli mixture models", but have not found a solution.

Below I share some results from a simulation that I have written and played around with.

• p(r)=p(b)=0.7
• p(Kr)=p(Kb)=0.5

Attempted 10,000 boxes with max of 20 attempts on each box.

• overall success rate 0.9102 (expected 0.91)
• red key successful 4446 times, blue key 4656 times
• Overall red key failures, 17,998. Blue key failures 17,575
• Key attempts in failed cases (giving up after 20 events)
• red key attempted 9091 times, blue attempted 8869 times
• data on red key successes
• 4446 successes (noted above)
• 3294 red key failures before success was seen
• 5225 blue key failures before red key has success
• data on blue key successes
• 4656 blue key successes (noted above)
• 3481 blue key failures before success was seen
• 5613 red key failures before blue key has success

From these I can ATTEMPT to determine p(Kr) and p(Kb). I get:

p(Kr)=4446./(4446 + 3294) = 0.5744186

similarly

p(Kb)=4656./(4656+3481) = 0.5722010

both of which are higher than 0.5 that I had expected. And I am not close to guessing p(r) and p(b) yet. All hints welcome.

Based on a large number of observations I would like to know if I can correctly determine my 4 probability values.

You can, with the following algorithm.

1. Draw a box, $i$
2. Try the blue key $Q$ times or until it opens the box.
3. If it opens the box, store the number of trials it took, $X_{i,b}$, and that the box contained a blue marble, $B_{i, b} = 1$
4. If it does not open the box after $Q$ attempts, no blue marble is in it with high probability (larger Q makes it more likely, but smaller key success probability makes it less likely) . Either a red marble is in it, or none.
5. Try the red key $Q$ times or until it opens the box.
6. If it opens the box, store the number of trials it took, $X_r$, and that the box contained a red marble $B_{i, r} = 1$.
7. If it doesn't it's empty (with high probability).

Repeat this process $S$ times. Compute the estimators for the 4 probabilities as follows:

$\widehat{\Pr (b)} = S^{-1} \sum_i^S B_{i,b}$

$\widehat{\Pr (r)} = S^{-1} \sum_i^S B_{i,r}$

For the key success probabilities, use the maximum likelihood estimator for the parameter of a geometric distribution:

$\widehat{\Pr (Kb)} = \frac{n_b}{ \sum_i X_{i,b} }$

$\widehat{\Pr (Kr)} = \frac{n_r}{ \sum_i X_{i,r} }$

Where $n_b$ and $n_r$ are the number of data points you have, ie the number of times you repeatedly attempted to open the box with each key until finally succeeding. The $X_{i, color}$ are the number of trials until success it took for each of those.

If the key success probabilities are likely small, $Q$ needs to be large to avoid upwards biasing their estimators and downwards biasing the marble colour estimators. In your example these are large so $Q=20$ as you have is enough. But it obviously won't be when the success probability is eg $1/1000$

• It seems this method would work and I will run a simulation of it and report back what I see. I do have a few comments. 1) Can I alternate which color I attempt first (your step 2)? I don't think it seems right to always try 1 color first. This is esp. true given my other condition that once a box is open we can not try the key of other color. This means your step "5" is conditional on failing to open w/ color that I start w/ first. 2) All 4 probability values will be in the range of 0.9 to 0.1, perhaps this helps. – George Nov 8 '16 at 16:34
• 3) In your step 6 I think it should be X(i,r), noted. I believe X(i,color) will not count any attempts which resulted ultimately in failure to open a box. – George Nov 8 '16 at 16:35
• 4) One reason I would like to alternate which color I try first is that my data is gathered in a live situation, I would like to not only estimate these 4 probabilities but the goal is to minimize the expected number of attempts I make before opening boxes. Let us say my goal is to open 100 or 1k or 10k boxes, would like to do it with minimal/low number of attempts. Any time we know the 4 probabilities we precompute an optimal sequence of key attempts, but here we don't know these 4 values and are trying to estimate them as we go along, possibly refining our order of key we try as we learn. – George Nov 8 '16 at 16:37
• 5) It seems that a solution will require trying 1 color till success/failure and then try the 2nd color (if failure w/ 1st color). If one tries keys randomly against a single box I believe fundamentally the algorithm breaks down and may be it is not possible to find these 4 values w/ random sequence of key attempts. Thoughts? Once again, thank you very much. – George Nov 8 '16 at 16:37
• I've coded this in a simple python simulation and it works for any combination of the 4 probabilities, provided you make Q large enough if the key probs are small. For step 5. yeah I forgot to mention: If the box is upowned, try the red key. If it was opened, draw a new box. Else you will bias downwards the probability of the red marble. – CloseToC Nov 8 '16 at 23:35