Reliability of a system is an important aspect of any system design since any user of the system would expect some type of guarantee that the system will function to some level of confidence. Failing to meet such guarantee will result in disastrous consequences. On the other hand, overly exceeding such guarantee level may incur additional and unnecessary expense to the developers. Moreover, for any non-trivial software system, an exhaustive testing among the entire input domain can be very expensive. By adopting the partition testing strategy, we attempt to break up the testable input domain of possible test cases into partitions, which must be non-overlapping, such that if test case $i$ belongs to partition $j$ , then no partition other than $j$ will contain $i$ . Sayre and Poore^1–11 have given several possible mechanics to partition the domain into finitely many subdomains, $X_{ij}=\{\begin{array}{c}1,\text{if test}j\text{taken from partition}i\text{is processed correctly}\\ 0,\text{otherwise}\end{array}$ , such that :
$D=\underset{i=1}{\overset{k}{{\displaystyle \cup }}}{D}_i;D_i\cap D_j=\varnothing ,i\ne j$ which allows us to define the system reliability by a weighted sum of reliabilities of these  subdomains, i.e.
$R={\displaystyle \sum }_{i=1}^k{p}_i{R}_i$ Where $R$ denotes the system reliability $R_i$ and is the reliability of each subdomain $D_i$ ; and $p_i$ , parameters of the operational profile is the likelihood of this test case belongs to partition $D_i$ , which are assumed to be known.¹²  As mentioned above, a complete testing of any software system of non-trivial size is practically impossible, $R_i$  are usually unknown parameters to us. So as to gain knowledge about $R_i$ , we must distribute the $k$ test cases among these $k$ partitions, and generate reasonable estimates for each. Specifically, we denote $n_1,n_2,\dots ,n_k$ as sizes of the samples which are taken from sub domain $D_1,D_2,\dots ,\text{'}{D}_k$

, respectively, where $${\sum }_{i=1}^k{n}_i=N$$

We model the outcome of the $j^{th}$ taken from the $i^{th}$ partition as a Bernoulli random variable $X_{ij}$ such that:

and each $X_{ij}$ follows a Bernoulli distribution with parameter $R_i$ . Then, the estimate of the overall system reliability, $R$ denoted by $\widehat{R}$ can thus be defined as:

Ideally, we would like to execute all possible test paths through the software and determine the true overall reliability of the system. In practice though, resources are often limited, sample test cases must be chosen and allocated strategically to attain the best reliability estimate possible given all kinds of constraints. One of the criteria of distributing test cases among the  partitions, which proceeds from rewriting (1.1) as follows:

$Var\left(\widehat{R}\right)=\frac{{\left[{{\displaystyle \sum }}_{i=1}^k{p}_i\sqrt{R_i\left(1-R_i\right)}\right]}^2}{N}+\frac{1}{N}{\displaystyle \sum }_{i=1}^{k-1}{\displaystyle \sum }_{j=i+1}^k\frac{{\left[n_i{p}_j\sqrt{R_j\left(1-R_j\right)}-n_j{p}_i\sqrt{R_i\left(1-R_i\right)}\right]}^2}{n_i{n}_j}$

which is bounded below by the first term:

$Var\left(\widehat{R}\right)\ge \frac{{\left[{{\displaystyle \sum }}_{i=1}^k{p}_i\sqrt{R_i\left(1-R_i\right)}\right]}^2}{N}$

with equality of (2.1) to hold is and only if:

$\frac{n_i}{n_j}=\frac{p_i\sqrt{R_i\left(1-R_i\right)}}{p_j\sqrt{R_j\left(1-R_i\right)}}$

for all . Hence, the optimal allocation is determined by:

$\frac{n_i}{N}=\frac{p_i\sqrt{R_i\left(1-R_i\right)}}{{{\displaystyle \sum }}_{j=1}^k{p}_j\sqrt{R_j\left(1-R_i\right)}}$

for $i=1,2,\dots ,k-1$ , and

$n_k=N-\underset{i=1}{\overset{k-1}{{\displaystyle \rangle }}}{n}_i$

and the variance incurred by this optimal allocation is:

$Var\left(O\right)=\frac{{\left[{{\displaystyle \sum }}_{j=1}^k{p}_j\sqrt{R_j\left(1-R_i\right)}\right]}^2}{N}$

Note that the optimal allocation depends on the actual reliabilities $R_1,R_2,\dots ,R_k,$ which are unknown. Therefore the optimal sampling scheme is not practical.  It is this shortcoming that motivates us to adopt such dynamic allocation approaches that will be discussed in the following three sections.

By adopting a fully Bayesian approach with Beta priors, Rekab, Thompson and Wei⁵ proposed a fully sequential design shown to be first order optimal.  The fully sequential design is defined as follows;

We first test one case from each of the  partitions and estimate the reliability for each of these partitions.

Stage 1:

After  cases have been allocated, $l\ge k,$ the next test will be taken from partition $i$ if for all $j$
, 

$\frac{n_{l,i}}{n_{l,j}}<\frac{p_i\sqrt{{\widehat{R}}_{l,i}\left(1-{\widehat{R}}_{l,i}\right)}}{p_j\sqrt{{\widehat{R}}_{l,j}\left(1-{\widehat{R}}_{l,j}\right)}}$

where $n_{l,i}$ is the cumulative test cases allocated to partition $i$ after $l$ tests have been allocated and the current  estimated reliability for partition $i$ is determined by:

${\widehat{R}}_{l,i}=\frac{{{\displaystyle \sum }}_{m=1}^{n_{l,i}}{X}_{im}}{n_{l,i}}$

Stage 2:

Repeat step 2 sequentially until all the  test cases are allocated, and the final estimate of reliability for partition  is:

${\widehat{R}}_i=\frac{{{\displaystyle \sum }}_{m=1}^{n_{N,i}}{X}_{im}}{n_{N,i}}$

And thus, the estimate of the overall reliability of the system is:

$\widehat{R}=\underset{i=1}{\overset{k}{{\displaystyle \rangle }}}{p}_i{\widehat{R}}_i$

By adopting a fully Bayesian approach with Beta priors, Rekab, Thompson & Wei⁶ proposed a multistage sequential design shown to be first order optimal.  Instead of making an allocation decision for each test at a time, the multistage sequential sampling allocates  test cases among the partitions in  stages in batches, where  and   are both pre-specified. The multistage sequential design is defined as follows:

Stage 1:

We start with an initial sample of  test cases, which are allocated among the  partitions with a balanced allocation scheme, such that:

$S_{1,i}=\frac{S_1}{k}$

and estimate the reliability for partition  by:

${\widehat{R}}_{1,i}=\frac{{{\displaystyle \sum }}_{m=1}^{s_{1,i}}{X}_{im}}{S_{1,i}}$

Therefore,

${\widehat{C}}_i\left(S_1\right)=\frac{p_i\sqrt{{\widehat{R}}_{1,i}\left(1-{\widehat{R}}_{1,i}\right)}}{{{\displaystyle \sum }}_{j=1}^k{p}_j\sqrt{{\widehat{R}}_{1,j}\left(1-{\widehat{R}}_{1,j}\right)}}$

Stage 2 through L:

At stage$j,$ for partition the test cases are distributed by the following way:

the test cases are distributed by the following way:

$S_{j,i}=\left(\underset{l=1}{\overset{j}{{\displaystyle \rangle }}}{S}_l\right){\widehat{C}}_i\left({\overline{S}}_{j-1}\right);$

and

$S_{j,k}=\underset{l=1}{\overset{j}{{\displaystyle \rangle }}}{S}_l-\underset{i=1}{\overset{k-1}{{\displaystyle \rangle }}}{S}_{j,i}$

where

${\overline{S}}_{j-1}=\underset{y=1}{\overset{j-1}{{\displaystyle \rangle }}}{S}_y$

At the final stage , the cumulative number of tests allocated to partition  is:

$N_i=\min \left\{N-\underset{j=1,j\ne i}{\overset{k-1}{{\displaystyle \rangle }}}{S}_{L-1,j},\max \left(N{\widehat{C}}_i\left({\overline{S}}_{L-1}\right),S_{L-1,i}\right)\right\}$

and

$N_k=N-\underset{i=1}{\overset{k-1}{{\displaystyle \rangle }}}{N}_i$

Among several ways of determining the number of cases at each sampling stage, the simplest one is to select:

$S_1=S_2=\dots =N/L$

However, choosing stage sizes, especially the  initial stage size, can be done by following some general criteria,  a good initial stage size can be $\sqrt{N}$  for when a  two stage sampling scheme is considered, and more generally, Rekab⁹ shows that for  a two stage procedure,  must be chosen such that:

$\underset{N\to \infty }{\lim }{S}_1=\infty ,and\underset{N\to \infty }{\lim }\frac{S_1}{N}=0$

By adopting a fully Bayesian approach with Beta priors, Rekab, Thompson and Wei⁶ proposed an accelerated sequential design shown to be first order optimal. The accelerated sampling scheme combines the fully sequential sampling scheme and the multistage sampling scheme. It is defined as follows:

Stage 1:

The procedure starts with an initial sample $S_1$ , which satisfies the conditions specified in (4.1). Then, allocate $S_1$  equally among   partitions   

Stage 2 through $L-1$

At stage $j$$2\le j\le L-1,$ for partition $i=1,2,\dots ,k-1,$ the test cases are distributed by the following way:

$S_{j,i}=\left(\underset{l=1}{\overset{j}{{\displaystyle \rangle }}}{S}_l\right){\widehat{C}}_i\left({\overline{S}}_{j-1}\right);$

and

$S_{j,k}=\underset{l=1}{\overset{j}{{\displaystyle \rangle }}}{S}_l-\underset{l=1}{\overset{k-1}{{\displaystyle \rangle }}}{S}_{j,i}$

where

${\overline{S}}_{j-1}=\underset{y=1}{\overset{j-1}{{\displaystyle \rangle }}}{S}_y$

At each stage, $S_j$  must satisfy the two conditions as $S_1$ .

Stage L:

In the final stage, we adopt a fully sequential approach by allocating one test from partition , if for all ,

$\frac{n_{l,i}}{n_{l,j}}<\frac{p_i\sqrt{{\widehat{R}}_{l,i}\left(1-{\widehat{R}}_{l,i}\right)}}{p_j\sqrt{{\widehat{R}}_{l,j}\left(1-{\widehat{R}}_{l,j}\right)}}$

until all the test cases have been allocated. Note that $n_{l,i}$ , $n_{l,i}$ are the cumulative test cases allocated to partition  and  after the allocations of a total of  test cases, where

${\displaystyle \sum }_{j=1}^{L-1}{S}_{j,i}\le l\le {\displaystyle \sum }_{j=1}^{L-1}{S}_{j,i}+N-{\displaystyle \sum }_{j=1}^{L-1}{S}_j$

Therefore, the estimate for the whole system is finally obtained as:

First order optimality of these three sequential designs was established by Rekab, Thompson & Wu,^5–7 although the focus here is on minimizing the variance incurred by the sequential designs rather than minimizing the Bayes risk incurred by these designs. For estimating the mean difference of two independent normal populations, Woodroofe and Hardwick¹² adopted a quasi-Bayesian approach. They determined an asymptotic lower bound for the integrated risk and proposed a three-stage design that is second-order optimal.  For estimating the mean difference of two general one -parameter exponential family, Rekab and Tahir¹⁰ adopted a fully Bayesian approach with conjugate priors. They determined an asymptotic second order lower bound for the Bayes risk.

We consider the case where the test domain is partitioned into two subdomains $D_1$  and $D_2$ with reliability $R$  and $R_2$ respectively with equal usage probabilities $p_1,p_2.$ Second order optimality of the three sequential designs is investigated through Monte Carlo simulations.

Table I, II, III seem to indicate that the speed $N^2*\left(Var\left(\Delta \right)-Var\left(O\right)\right)$ is bounded.

Second optimal designs are more efficient than the first order optimal designs especially when the total number of cases is very large. This is the main argument that led us to investigate the second order optimality of these three dynamic designs. Simulation studies seem to indicate that these designs are second order optimal.  We conjecture that second order optimally may be obtained theoretically as well.

It is very common in parametric estimation to use the squared error loss. However, in reliability estimation one should distinguish between the cost of overestimating and underestimating the system reliability.    Examples of practical loss functions were presented by Stüger:²

$l\left(\widehat{R},R\right)=c_o{\left(\widehat{R}-R\right)}^2{I}_{\left\{\widehat{R}>R\right\}}+c_u{\left(R-\widehat{R}\right)}^2{I}_{\left\{\widehat{R}<R\right\}}$

and by Granger:¹

$l\left(\widehat{R},R\right)=c_o\left(\widehat{R}-R\right)I_{\left\{\widehat{R}>R\right\}}+c_u\left(R-\widehat{R}\right)I_{\left\{\widehat{R}<R\right\}}$

where represents the overestimation and underestimation costs, respectively.