0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – George Nov 8 '16 at 16:34
  • $\begingroup$ 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. $\endgroup$ – George Nov 8 '16 at 16:35
  • $\begingroup$ 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. $\endgroup$ – George Nov 8 '16 at 16:37
  • $\begingroup$ 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. $\endgroup$ – George Nov 8 '16 at 16:37
  • $\begingroup$ 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. $\endgroup$ – CloseToC Nov 8 '16 at 23:35

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.