You probably know of the egg drop problem where you have eggs and drop them at different heights (floors of a building) and have to find the threshold height above which the eggs break (the eggs always break at the same height). You can solve this by treating it as a binary search problem.
But what about if the egg breaking is probabilistic? I make up two scenarios: "occasionally strong eggs", "occasionally weak eggs"
In the "occasionally strong eggs" case, take the original deterministic case and modify it as follows: Now, instead of always breaking when dropped from floor > F, for drops above floor F, there is now some probability P that the egg actually will NOT break. But as before assume it never breaks when dropped at or below floor F.
In the "occasionally weak eggs" case, take the original deterministic case and modify it as follows: Now, instead of never breaking when dropped from floor <= F, for drops at or below floor F, there is now some probability Q that the egg actually WILL break. But assume as before it always breaks when dropped above floor F.
How would you solve the egg drop problem here? I think for a finite number of egg drops you only be able to reach your conclusions probabilistically, e.g. I know to within C=99% confidence that this floor is the threshold. Since e.g. the "real" floor in the weak eggs case could be floor 200 and every drop from above there also broke, but in your finite amount of egg drops for floors 190-200 they also always broke so you might think the "real" floor is floor 189.
Simplifications: I guess for now we should say we know before hand what fixed P or Q is instead of also having them as unkowns or thinking from A bayesian perspective and treating them as random variables.
So one way I was thinking is do binary search as before but for a given partitioning of the search space in half, instead of just dropping a single time and knowing for sure whether it broke or not, you treat it as a Bernoulli trial with probability P, and in order to be able to say with probability C if this floor is above/below the threshold floor F, you repeat K times such that 1 - (1-P)^K >= C, or something similar to that treating it as indpendent bernoulli trials...
Also, maybe you can actually combine these two scenarios if you change around P and Q or something...
Would appreciate any answers to either problem or thoughts about it. Or solutions with extensions to not treating P or Q as fixed [so you might also have to estimate P or Q as an intermediate step].