3
$\begingroup$

Suppose a quality inspector is inspecting $b$ black amongst which $d_B$ are known to be defective and $w$ white gadgets amongst which $d_W$ are known to be defective. The gadgets come down along an assembly line one by one in uniformly distributed random order. As each gadget passes, the inspector observes its color, and he chooses to let the gadget pass or use a device to detect whether the gadget is defective. But he can only use the device a total of $n$ times. What is the optimal stopping rule to use the inspecting device to maximize the expected number of defective gadgets found.

Edit: As fedja points out below, there is a difference between detecting a defect by the device and deducing for sure by logic a defect. Both are legitimate objectives. The solution to the first is easier than that to the second. I for now choose the first definition, i.e., to define finding a defective gadget as only indicated by the device and use up one quota of using the device even if the quality inspector is sure by logic alone the gadget under inspection is defective.

Suppose at a pass the number of black gadgets already inspected by the device is $i_B$, amongst them $f_B$ are detected to be defective. Suppose the current passing gadget is black and yet to be inspected. Then the probability of this black gadget being defective is $p_B=\frac{d_B-f_B}{b-i_B}$. Symmetrical probability holds for if the current passing gadget is white.

I have a conjecture for the explicit solution, which is a greedy algorithm, as follows and am seeking a proof.

At a pass of the gadget, without loss of generality, suppose the current gadget which has not yet been inspected is black. Suppose there are $n_B$ black including the current one and $n_w$ white gadgets left. Suppose $i_B$ black and $i_W$ white gadgets have been inspected, amongst which $f_B$ black and $f_W$ have been found to be defective. If $p_B\ge p_W$ or $n_W=0$ the inspector inspect the current black gadget with the device. Otherwise, the inspector let the current black gadget pass without inspection.

I have set up the dynamic programming formulation but fail to see either the proof or a counterexample to my conjecture.

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ Cross-posted here $\endgroup$
    – RobPratt
    Commented Jul 26, 2020 at 22:16
  • $\begingroup$ @RobPratt: It is just that so far it does not look like I can get an answer there. $\endgroup$
    – Hans
    Commented Jul 26, 2020 at 22:33
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/q/3769463/14578, mathoverflow.net/q/366646/37212, cstheory.stackexchange.com/q/47306/5038. Please do not post the same question on multiple sites. Please pick one. You can delete the question elsewhere if you decide you've posted it on the wrong site. $\endgroup$
    – D.W.
    Commented Jul 31, 2020 at 3:31
  • $\begingroup$ @D.W.: I noted the cross posting on the computer science site. That was how you came here. Also, 5 days have lapsed since I posted this question here before I post the question on the computer science site. Let me add more details to the question to answer your questions. $\endgroup$
    – Hans
    Commented Jul 31, 2020 at 3:43
  • 1
    $\begingroup$ It seems only the case when, at least one color, is all defective would make a difference. In the recursive formula, yes, but it changes the answer even in the cases when we haven't arrived at that situation yet but are potentially close to it. The "beep objective" results in a cleaner recursion and simpler boundary conditions, so let's stick to it for now: I still do not see how to finish even this case :-) $\endgroup$
    – fedja
    Commented Sep 6, 2020 at 6:17

1 Answer 1

Reset to default
0
$\begingroup$

I do not answer the ultimate question which is to prove or disprove the conjecture. But I hereby post the dynamic programming algorithm for solving any given set of parameters.

Let $\bigg(\begin{matrix}c_B&l_B&n_B \\c_W&l_W&n_W\end{matrix}\hspace{2ex} m\bigg)$ denote the maximal expected number of defects to be found with $n_B$ black and $n_W$ white gadgets to pass and $m$ inspections to use, where $c_B:=d_B-f_B$, $l_B:=b-i_B$, $c_W:=d_W-f_W$, $l_W:=b-i_W$. We obtain a recursion by conditioning on observing the color of the current passing gadget then taking the maximum of the expected maximum expectation of the defect detection based on maximizing the two choices of whether or not to use the device to detect the defect. At each pass of a gadget, the probability that the current gadget is black is $\frac{n_B}{n_B+n_W}$ while it is white is $\frac{n_W}{n_B+n_W}$. Conditioned on having observed the color of the passing gadget being black the probability of it being detected to be defective is $\frac{c_B}{l_B}$. Conditioned on having observed the color of the passing gadget being white the probability of it being detected to be defective is $\frac{c_W}{l_W}$. We have the recursion \begin{align} &\bigg(\begin{matrix}c_B&l_B&n_B \\c_W&l_W&n_W\end{matrix}\hspace{2ex} m\bigg) \nonumber \\[1ex] =&\ \ \frac{n_B}{n_B+n_W} \max \begin{cases} \frac{c_B}{l_B}\bigg(1+\bigg(\begin{matrix}c_B-1&l_B-1&n_B-1 \\c_W&l_W&n_W\end{matrix}\hspace{2ex} m-1\bigg) \bigg) +\Big(1-\frac{c_B}{l_B}\Big)\times \\ \quad\quad\bigg(\begin{matrix}c_B&l_B-1&n_B-1 \\c_W&l_W&n_W\end{matrix}\hspace{2ex} m-1\bigg) \\[4.5ex] \bigg(\begin{matrix}c_B&l_B&n_B-1 \\c_W&l_W&n_W\end{matrix}\hspace{2ex} m\bigg) \end{cases} \nonumber \\[2ex] &+ \frac{n_W}{n_B+n_W}\max \begin{cases} \frac{c_W}{l_W}\bigg(1+\bigg(\begin{matrix}c_B&l_B&n_B \\c_W-1&l_W-1&n_W-1\end{matrix}\hspace{2ex} m-1\bigg) \bigg) +\Big(1-\frac{c_W}{l_W}\Big)\times \\ \quad\quad\bigg(\begin{matrix}c_B&l_B&n_B \\c_W&l_W-1&n_W-1\end{matrix}\hspace{2ex} m-1\bigg) \\[4.5ex] \bigg(\begin{matrix}c_B&l_B&n_B \\c_W&l_W&n_W-1\end{matrix}\hspace{2ex} m\bigg) \end{cases} . \end{align}

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .