A simulated annealing algorithm for joint stratification and sample allocation
Section 3. The joint stratification and sample allocation
problem

• Previous
• Next

Our aim is to partition $L$ atomic strata into $H$ non-empty sub-populations or strata. A partitioning represents a stratification of the population. We aim to minimise the sample allocation to this stratification while keeping the measure of similarity less than or equal to the upper limit of precision, ${\epsilon }_g.$ This similarity is measured by the CV of the estimated population total for each one of $G$ target variable columns, ${\widehat{T}}_g.$ We indicate by $n_h$ the sample allocated to stratum $h$ and the survey cost for a given stratification is calculated as follows:

$$C\left(n_1,\dots ,n_H\right)={\displaystyle \sum _{h=1}^H{C}_h{n}_h}$$

where $C_h$ is the average cost of surveying one unit in stratum $h$ and $n_h$ is the sample allocation to stratum $h.$ In our analysis $C_h$ is set to 1.

The variance of the estimator is given by:

$$\text{VAR} \left({\widehat{T}}_g\right)={\displaystyle \sum _{h=1}^H{N}_h^2}\left(1-\frac{n_h}{N_h}\right)\frac{S_{h,g}^2}{n_h}\left(g=1,\dots ,G\right)$$

where $N_h$ is the number of units in stratum $h$ and $S_{h,g}^2$ is the variance of stratum $h$ for each target variable column $g.$

As mentioned above ${\epsilon }_g$ is the upper precision limit for the CV for each ${\widehat{T}}_g$:

$$\text{CV}\left({\widehat{T}}_g\right)=\frac{\sqrt{\text{VAR}\left({\widehat{T}}_g\right)}}{E\left({\widehat{T}}_g\right)}\le {\epsilon }_g.$$

The problem can be summarised in this way:

$$\begin{array}{ll}\text{min}\hfill & n={\displaystyle \sum _{h=1}^H{n}_h}\hfill \\ \text{subject}\text{to}\hfill & \text{CV}\left({\widehat{T}}_g\right)\le {\epsilon }_g\left(g=1,\dots ,G\right).\hfill \end{array}$$

To solve the allocation problem for a particular stratification with the Bethel-Chromy algorithm the upper precision constraint for variable $g$ can be expressed as follows:

$$\begin{array}{ll}\text{CV}{\left({\widehat{T}}_g\right)}^2\le {\epsilon }_g^2\hfill & \equiv {\displaystyle \sum _{h=1}^H\frac{N_h^2{S}_{h,g}^2}{n_h}}-N_h{S}_{h,g}^2\le E\left({\widehat{T}}_g^2\right){\epsilon }_g^2\hfill \\ \hfill & \equiv {\displaystyle \sum _{h=1}^H\frac{N_h^2{S}_{h,g}^2}{\left(E\left({\widehat{T}}_g^2\right){\epsilon }_g^2+{\displaystyle {\sum }_{h=1}^H{N}_h{S}_{h,g}^2}\right)n_h}}\le 1.\hfill \end{array}$$

Then we substitute

$$\frac{N_h^2{S}_{h,g}^2}{\left(E\left({\widehat{T}}_g^2\right){\epsilon }_g^2+{\displaystyle {\sum }_{h=1}^H{N}_h{S}_{h,g}^2}\right)}$$

with ${\xi }_h,g$ and replace the problem summary with the following:

$$\begin{array}{l}\text{min}n={\displaystyle \sum _{h=1}^H{n}_h}\\ {\displaystyle \sum _{h=1}^H\frac{{\xi }_h,g}{n_h}}\le 1\left(g=1,\dots ,G\right)\end{array}$$

where $\frac{1}{n_h}>0.$ The Bethel-Chromy algorithm uses Lagrangian multipliers to derive a solution for each $n_h.$

$$\frac{1}{n_h}=\{\begin{array}{ll}\frac{\sqrt{1}}{\left(\sqrt{{\displaystyle {\sum }_{g=1}^G{\alpha }_g{\xi }_h,g}}{\displaystyle {\sum }_{h=1}^H\sqrt{{\displaystyle {\sum }_{g=1}^G{\alpha }_g{\xi }_h,g}}}\right) }\hfill & \text{if}{\displaystyle \sum _{g=1}^{\text{G}}{\alpha }_g{\xi }_h\text{,}g}>0\hfill \\ +\infty \hfill & \text{otherwise}\hfill \end{array}$$

where

$${\alpha }_g=\frac{{\lambda }_g}{{\displaystyle {\sum }_{g=1}^G{\lambda }_g}},$$

and ${\lambda }_g$ is the Lagrangian multiplier (Benedetti et al., 2008). The algorithm starts with a default setting for each ${\alpha }_g$ and uses gradient descent to converge to a final value for them.

• Previous
• Article main page
• Next