# Stopping rule for quality control problem

Problem:

Suppose I have a production process that yields output in batches of $n$ items. For each batch, I can test whether they are of good or bad quality. Let $q_i\in\{1,0\}$ be the quality of tested item $i$.

If more than half of the items are ‘bad’, the batch should be discarded. In other words: the batch should be discarded if the average quality of items is $\bar{q}(n)<0.5$.

Suppose testing is sequential (i.e. you learn the quality of items one at the time), and each test is a random draw from a Bernoulli distribution with unknown mean $p$.

I would like to know when to stop testing items in a batch, in order to decide whether to discard it without testing all items, and yet be statistically confident that the outcome (discard vs not discard) is the same as the one that would have been reached if all items had been tested.

What I currently have:

If I knew $p$, I could use a normal approximation to estimate the confidence interval of the binomial proportion $\bar{q}(k)$ for any $k$. With this, for any arbitrary width of the interval, I could calculate the number of tests that are required to achieve a given confidence level (let me call such number of tests $k^*$).

Since I don’t know $p$, one option would be to solve for $k^*$ assuming the worst case scenario (i.e. $p=0.5$). This was proposed (and discussed) in a related question here.

This approach, however, does not take into account that $n$ is finite, so once many items have been tested, it becomes very unlikely that one more test will swing the outcome…

#### Solutions Collecting From Web of "Stopping rule for quality control problem"

Bayesian Approach

Samples $(q_i)_{i=1..k}$ are taken sequentially (without replacement) from a batch of size $n$ for the purpose of making inferences about $\bar{q}(n)$, the unknown proportion of “good” items in that batch. Two criteria are assumed:

1. A real number $acc\in(0,1)$ (e.g. $acc=0.5$) that serves to define the “acceptability” of a batch; specifically, the batch is considered unacceptable iff $\bar{q}(n) < acc$.
2. A real number $\epsilon\in(0,1)$ (e.g. $\epsilon=0.05$) that serves as an “effective convergence” criterion; specifically, if a sequence of probabilities $p_k$ is known to converge to either $0$ or $1$, it will be considered to have “effectively converged” to $0$ (resp. $1$) if $\ p_k \le \epsilon$ (resp. $\ p_k \ge 1-\epsilon$).

Sampling will therefore stop when $p_k$, the posterior probability of $\{\bar{q}(n)<acc\}$ given $(q_i)_{i=1..k}$, has “effectively converged” to $0$ or $1$ (as it must do for some $k\in 1..n$, because necessarily $p_n\in\{0,1\}$). Thus, the sequential procedure is as follows:

1. $k \leftarrow 0$.

2. $k \leftarrow k+1$; sample $q_k$, yielding $(q_i)_{i=1..k}$.

3. Compute the posterior distribution of the unknown $\bar{q}(n)$, given $(q_i)_{i=1..k}$.

4. Compute the posterior probability $p_k = P\big(\bar{q}(n)< acc\mid (q_i)_{i=1..k}\big)$.

5. If $p_k \le \epsilon$, decide $\{\bar{q}(n)\ge acc\}$; else if $p_k \ge 1-\epsilon$, decide $\{\bar{q}(n)< acc\}$; else goto (2).

Posterior distribution

Let $S_k = \sum_{i=1}^k q_i = k\,\bar{q}(k)$ for $k\in 0..n$. Now

\begin{align} &P\{S_n\!=\!t\mid S_k\!=\!s\} \\ &= \int_0^1 P\{S_n\!=\!t\mid S_k\!=\!s, p\!=\!p’\}\,f_{p\mid S_k}(p’\mid s)\,dp’\tag{A1}\\ &= \int_0^1 P\{S_n\!=\!t\mid S_k\!=\!s, p\!=\!p’\}\,\frac{P\{S_k\!=\!s\mid p\!=\!p’\}f(p’)}{\int_0^1 P\{S_k\!=\!s\mid p\!=\!p”\}f(p”)dp”}\,dp’\tag{A2}\\ \end{align}

where

\begin{align} &P\{S_n\!=\!t\mid S_k\!=\!s, p\!=\!p’\}= \binom{n-k}{t-s}(p’)^{t-s}(1-p’)^{n-k-(t-s)}I_{\{s,…,s+n-k\}}(t)\tag{B1}\\ &P\{S_k\!=\!s\mid p\!=\!p’\}= \binom{k}{s}(p’)^s(1-p’)^{k-s}I_{\{0,…,k\}}(s)\tag{B2}\\ \end{align}
and $f()$ is the prior density for $p$. For the sake of modeling various potential prior states of knowledge about $p$, we use a Beta distribution with positive real parameters $\alpha, \beta$ (with $\alpha=\beta=1$ producing a uniform distribution):
$$f(p’) = \frac{1}{\mathrm{B}(\alpha,\beta)}(p’)^{\alpha-1}(1-p’)^{\beta-1}I_{(0,1)}(p’)\tag{B3}$$
where
$$\mathrm{B}(\alpha,\beta)= \int_0^1(p’)^{\alpha-1}(1-p’)^{\beta-1}\,\mathrm{d}p’=\dfrac{\Gamma(\alpha)\,\Gamma(\beta)}{\Gamma(\alpha+\beta)} .$$
Note that (B1) describes the fact that, conditional on $S_k\!=\!s,\ p\!=\!p’$,
$$S_n\,=\,S_k + \sum_{i=k+1}^n q_i\ \sim\ s + \text{Binomial}(n-k,p’).$$
and that (B2) describes the fact that, conditional on $p\!=\!p’$,
$$S_k\,\sim\,\text{Binomial}(k,p’).$$

Substituting (B) into (A) and performing the integrations gives the posterior distribution in terms of a binomial coefficient and standard Beta functions, for any $s\in 0..k$ and $k\in 0..n$:

\begin{align} &P\{S_n\!=\!t\mid S_k\!=\!s\} = \binom{n-k}{t-s}\ \frac{\mathrm{B}(\alpha+t,\ \beta+n-t)}{\mathrm{B}(\alpha+s,\ \beta+k-s)}\ I_{\{s,…,s+n-k\}}(t).\tag{C1}\\ \end{align}

Finally,

\begin{align} p_k &= P\big(\bar{q}(n)<acc\mid (q_i)_{i=1..k}\big)\\ &= \sum_{t\ <\ acc\cdot n}P\{S_n\!=\!t\mid S_k\!=\!s\}.\tag{C2} \end{align}

NB: When $k=0$, we have $P(S_n=t\mid S_0=0)$ and $p_0$, which are the prior (before-sampling) probabilities of $\{S_n=t\}$ and $\{\bar{q}(n)<acc\}$, respectively, deriving entirely from the $\text{Beta}(\alpha,\beta)$ prior assigned to the Bernoulli process parameter $p$. (Extremely “informative” priors may result in $p_0$ effectively equal to $0$ or $1$, hence accepting or rejecting the batch even before any sampling is done.)

Implementation in SageMath

# pr(S_n = t | S_k = s)
def P(t,n,k,s,a,b): return binomial(n-k,t-s) * beta(a+t,b+n-t) / beta(a+s,b+k-s)

# pr(S_n < acc*n | S_k = s)
def Pun(acc,n,k,s,a,b):
tot = 0; accn = acc*n
for t in [s..s+n-k]:
if t < accn: tot += P(t,n,k,s,a,b)

# example
n = 20; acc = 0.5
a = 1; b = 1

# display the posterior probabilities pr(S_n < acc*n | S_k = s)
for k in [0..n]:
print "k=%3d:   " % k,
for s in [0..k]:
print "%.2f" % Pun(acc,n,k,s,a,b),
print


Example

Here’s a picture of the decisions that would be made in the case of a non-informative (uniform) prior for $p$, batch size $n=20$, criteria $acc=0.5,\ \epsilon=0.05$ (computations programmed in Sage):

Laplace’s “Rule of Succession”

Note that the present Beta-Binomial model exhibits Laplace’s “Rule of Succession” as a special case of equation (C1) (changing $n\to n+1,\ k\to n$):
$$P(S_{n+1}=s+1 \mid S_n=s) = \frac{s+\alpha}{n+\alpha+\beta}.$$