void	g05nfc (Integer rtype, Integer n, const double wt[], const Integer ipop[], Integer m, Integer nrs, Integer otype, Integer isampl[], Integer pdisampl, Integer state[], NagError *fail)

The function may be called by the names: g05nfc or nag_rand_resample.

3 Description

Given a vector

V

, of

n

integer values, g05nfc selects

m

elements with the probability of selecting

V_{j}

proportional to a user-supplied weight,

w_{j}

. The sampling is done with replacement, so that each value,

V_{j}

, may appear more than once in the sample.

The most common usage case for g05nfc is where

V

was obtained using some other sampling method, for example, importance sampling. In such a case, this function is used to perform resampling.

Several methods of calculating

N_{j}

, the number of times

V_{j}

appears in the sample, are available:

•Multinomial Resampling: The vector of counts; ${N_{j} : j = 1, 2, \dots, n}$ is drawn from a multinomial distribution with probabilities given by the normalised weights, $\tilde{w}$ .
•Systematic Resampling:

$N_{j} = | {u_{i} : i = 1, 2, \dots, m and \sum_{k = 1}^{j - 1} {\tilde{w}}_{k} < u_{i} \leq \sum_{k = 1}^{j} {\tilde{w}}_{k}} |$

where $\tilde{w}$ are the normalised weights, $u_{1} \sim U (0, \frac{1}{m})$ , $u_{i} = u_{1} + \frac{i - 1}{m}$ , for $i = 2, 3, \dots, m$ and $\sum_{k = 1}^{0} {\tilde{w}}_{k}$ is defined to be zero. In other words, $N_{j}$ is the number of shifted and scaled uniform variates contained in bins defined by the partial sums of normalised weights.
•Residual Resampling: $N_{j} = N_{j}^{S} + N_{j}^{R}$ , where $N_{j}^{S} = ⌊ m {\tilde{w}}_{j} ⌋$ (i.e. the integer part of $m {\tilde{w}}_{j}$ ), and the vector of residual counts, ${N_{j}^{R} : j = 1, 2, \dots, n}$ is drawn from a multinomial distribution with probabilities given by ${{\tilde{w}}_{j} - \frac{N_{j}^{S}}{m} : j = 1, 2, \dots, n}$ .

See g05tgc for more information on the multinomial distribution and Douc et al. (2005) for more details on the resampling methods.

If multiple samples are requested (

nrs > 1

) then the chosen resampling method is performed independently for each sample.

One of the initialization functions g05kfc (for a repeatable sequence if computed sequentially) or g05kgc (for a non-repeatable sequence) must be called prior to the first call to g05nfc.

4 References

Douc R, Cappe O, and Moulines E (2005) Comparison of resampling schemes for particle filtering Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis 64–69 https://dx.doi.org/10.1109/ISPA.2005.195385

Li T, Bolic M, and Djuric P M (2015) Resampling Methods for Particle Filtering: Classification, implementation, and strategies IEEE Signal Processing Magazine vol. 32, no. 3 70–86 https://dx.doi.org/10.1109/MSP.2014.2330626

5 Arguments

1: $rtype$ – Integer Input

On entry: a flag indicating the resampling method to use.

$rtype = 1$: Multinomial resampling will be used.
$rtype = 2$: Systematic resampling will be used.
$rtype = 3$: Residual resampling will be used.

Constraint:

rtype = 1

2

3

2: $n$ – Integer Input

On entry:

n

, the size of the population.

Constraint:

n \geq 0

3: $wt [n]$ – const double Input

On entry:

w_{i}

, the weights. These weights need not sum to

1.0

Constraints:

$wt [i - 1] \geq 0.0$ , for $i = 1, 2, \dots, n$ ;
at least one (and preferably more than one) weight must be nonzero.

4: $ipop [\dim]$ – const Integer Input

Note: the dimension, dim, of the array ipop must be at least

$n$ , when $ipop is not NULL$ ;
otherwise $ipop$ is not referenced and may be NULL.

On entry:

V

, the vector to be sampled from. If

ipop is NULL

then the

V

is assumed to be the set of values

(1, 2, \dots, n)

Elements of ipop with the same value are not combined, therefore, if

wt [i] \neq 0, wt [j] \neq 0

and

i \neq j

then there is a nonzero probability that the sample will contain both

ipop [i]

and

ipop [j]

, irrespective of their values.

If the values to be returned in isampl are counts, i.e.,

otype = 2

, then ipop is not referenced.

5: $m$ – Integer Input

On entry:

m

, the size of the sample required.

Constraint:

m \geq 0

6: $nrs$ – Integer Input

On entry: the number of times to resample.

Constraint:

nrs \geq 0

7: $otype$ – Integer Input

On entry: a flag indicating what is returned in isampl.

$otype = 1$: The values returned in isampl are taken from the population.
$otype = 2$: The values returned in isampl are counts.

See isampl for more information.

Constraint:

otype = 1

2

8: $isampl [pdisampl \times nrs]$ – Integer Output

Note: where

ISAMPL (j, k)

appears in this document, it refers to the array element

isampl [(k - 1) \times pdisampl + j - 1]

On exit: the selected samples.

otype = 1

then each column of ISAMPL contains the

m

values from

V

that make up the sample. If

otype = 2

then

ISAMPL (j, k)

contains the number of times that

V_{j}

appears in the

k

th sample.

9: $pdisampl$ – Integer Input

On entry: the stride separating matrix row elements in the array isampl.

Constraints:

if $otype = 1$ , $pdisampl \geq m$ ;
otherwise $pdisampl \geq n$ .

10: $state [\dim]$ – Integer Communication Array

Note: the dimension,

\dim

, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument state in the previous call to nag_rand_init_repeatable (g05kfc) or nag_rand_init_nonrepeatable (g05kgc).

On entry: contains information on the selected base generator and its current state.

On exit: contains updated information on the state of the generator.

11: $fail$ – NagError * Input/Output

The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_ARRAY_SIZE: On entry, $m = ⟨ value ⟩$ , $otype = 1$ and $pdisampl = ⟨ value ⟩$ .
Constraint: $pdisampl \geq m$ .

On entry, $n = ⟨ value ⟩$ , $otype = 2$ and $pdisampl = ⟨ value ⟩$ .
Constraint: $pdisampl \geq n$ .
NE_BAD_PARAM: On entry, argument $⟨ value ⟩$ had an illegal value.
NE_INT: On entry, $m = ⟨ value ⟩$ .
Constraint: $m \geq 0$ .

On entry, $n = ⟨ value ⟩$ .
Constraint: $n \geq 0$ .

On entry, $nrs = ⟨ value ⟩$ .
Constraint: $nrs \geq 0$ .

On entry, $otype = ⟨ value ⟩$ .
Constraint: $otype = 1$ or $2$ .

On entry, $rtype = ⟨ value ⟩$ .
Constraint: $rtype = 1$ , $2$ or $3$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_INVALID_STATE: On entry, state vector has been corrupted or not initialized.
NE_NEG_WEIGHT: On entry, $i = ⟨ value ⟩$ and $wt [i - 1] = ⟨ value ⟩$ .
Constraint: $wt [i - 1] \geq 0.0$ .
NE_NO_LICENCE: Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_NON_ZERO_WEIGHTS: On entry, all the weights are zero.
Constraint: at least one weight must be nonzero.
NW_POTENTIAL_PROBLEM: There was no random component to the sample. Check the sample size and weights are as expected.
Specifically, check that more than one weight is nonzero. If $rtype = 3$ , also check the combination of m and weights.

7 Accuracy

Not applicable.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.

g05nfc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.

Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

It should be noted that whilst a given sample is a random selection from

V

, the ordering of the sample within isampl may not be. For example, when

otype = 1

the values returned are likely to be in the same order that the values appear in

V

. If it is important that the returned values represent a random sample from

V

rather than a ordered random sample then each sample should be randomly permuted via a subsequent call to g05ncc. The same applies to the order in which multiple samples are returned. One consequence of this is that if you call g05nfc once with

nrs = 1

, say, and then again (using the same initial values for state), with

nrs = 2

the first column of ISAMPL may not be the same in both cases since, on the second call, the sample from the first call may be returned in the second column rather than the first.

See also g05ndc, g05nec and g05tlc for other types of sampling.

10 Example

This example draws five samples of twenty five from a population of the same length and prints out the values.

g05nf: FL CL CPP AD PY MB

NAG CL Interfaceg05nfc (resample)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG CL Interface
g05nfc (resample)