Spatial Sampling Designs - Sampling Spatial Units for Agricultural Surveys - page 164

A π ¼ AI s : ð 7 : 9 Þ

ʓ \ ʛ

, Chauvet and Till ´ ( 2006 ) proposed a

To randomly select a vertex of

ʓ \ ʛ:
The algorithm consists of two main procedures: the flight and landing phases.
During the first phase, the constraints are always exactly satisfied. The objective is
to randomly round-off almost all the π k s to 0 or 1. The landing phase addresses the
fact that Eq. ( 7.9 ) cannot always be exactly satisfied.
The steps of the flight phase are as follows. The starting value is

sequence of random displacements in

π ðÞ ¼ π . For

each iteration t ¼0, ... , T :

1. Generate a vector u( t ) ¼ { u k ( t )} 6 ¼0, not necessarily random, such that u( t )
belongs to the kernel 1 of A (i.e., ker(A)) and u k ( t ) ¼0if π k ( t ) is an integer.

ʻ 1 and ʻ 2 ) such that 0 π 2. Compute the largest values of ʻ 1 ( t ) and ʻ 2 ( t )( ( t )+ ʻ 1 ( t )

u( t ) 1 and 0 π ( t ) ʻ 2 ( t )u( t ) 1, obviously ʻ 1 ( t ) > 0 and ʻ 2 ( t ) > 0.

3. Compute the next π using

1 uðÞ

Þ ¼ π

ðÞþʻ with probability ʴ ðÞ

π ð t þ 1 ; ð 7 : 10 Þ

2 uðÞ

π ðÞʻ with probability 1- ʴ ðÞ

2 .
The three steps are iterated until we cannot perform Step 1. In the flight phase,
finding a vector in ker(A) can be quite computationally expensive. To overcome
this difficulty, Chauvet and Till ´ ( 2006 ) developed a faster algorithm for
implementing the three steps. The idea consists of replacing A with a smaller
matrix B, where B is a sub-matrix of A containing only q + 1 columns of A. From
a technical point of view, a vector v of ker(B) can be used to find a vector u of
ker(A), because we can insert zeroes into v for each column of A that is not in B.All
the computations can be done using matrix B, which dramatically speeds-up the
algorithm. It can be shown that when the algorithm converges ( t ¼ T ), the following
three properties are satisfied:

2 = ʻ 1 þ ʻ

where ʴ ðÞ ¼ ʻ

1. E( .

2. A π ( T ) ¼A π .
3. The number of non-integer elements of

π ( T )) ¼ π

π ( T ) is at most equal to the number of

auxiliary variables.

*

At the end of the flight phase, the algorithm ends if π ¼ π ( T ) does not contain

any non-integer elements. In other words, π k ¼1 if the unit k is selected in the

sample and π k ¼0 otherwise. Otherwise, some constraints cannot be exactly satis-

fied. In the latter instance, the landing phase should be performed. One possible
method for the landing phase is to use an enumerative algorithm. In this case, the

1 The kernel of a matrix A, is the set of all vectors x for which Ax¼ 0.