Practical difference between "sampling" and "re-sampling with replacement"

Question

What is the difference between "sampling" and "re-sampling with replacement" from a practical point of view (I mean how do I code that) ?

When one say: "sampling $\tilde{x}_t^{(i)}$ from $p(x_t | x_{t-1}^{(i)})$", this mean that we generate $\tilde{x}_t^{(i)}$ from the conditional probability distribution $p(x_t | x_{t-1}^{(i)})$, so this is the next random value to generate from a uniform or a gaussian distribution for example, right ?

Now, when one say: "re-sampling with replacement N values $\{x_t^{(i)}; i=1,\dots,N\}$ from the set $\{\tilde{x}_t^{(i)}; i=1,\dots,N\}$ according to the associated weights/probabilities $\{w_i; i=1,\dots,N\}$". Does this mean that we choose each value $\tilde{x}_t^{(i)}$ according to the probability $w_i$, and repeat this until we get N values ? So how do you do that practically in a pseudo code ?

EDIT: I understand that re-sampling here means reselecting the values from the weighted set, by choose randomly, but according to the weights. So if we had three values, with weights 0.99, 0.005 and 0.005, then the most likely outcome of resampling would be three values of the first type. But how do I code this in a general case ?

Answer 1

I am going to try to expand my previous comment and correct some notation (let me know if I am mistaken). (Thanks for the suggestion @Macro)

1. In this case you need to know explicitely what $p(x_j\vert x_{j-1})$ means (Note that here $x_{j-1}$ is a known value and this distribution depends on this value somehow). An example of this is

$$x_j\sim \mbox{Normal}(x_{j−1},1).$$

In this case, in order to sample from $x_j$, you just need to sample from the a normal distribution with mean $x_{j−1}$ and variance $1$. For other examples you can check the wikipedia page for Markov chains or check other transition kernels.

2. A pseudocode for obtaining a sample of size $M$ with replacement is as follows

Starting with a known sample $\{x_i,i=1,...,N\}$, repeat $M$ times

(i). Consider partitioning the interval $(0,1)$ into $N$ subintervals $I_1=(0,w_1)$, $I_2=(w_1,w_1+w_2)$,..., $I_N = (\sum_{j=1}^{N-1}w_j,1)$.

(ii). Simulate $u\sim U(0,1)$.

(iii). Identify the interval $I_j$, $j\in\{1,...,N\}$, such that $u\in I_j$.

(iv). Take the sample $x_j$.

As you can see, there is a difference between these two methods.

In the first one you have a model, $p(x_{j}|x_{j−1})$ , and you simulate from it. Starting from, say $x_0$, the next value $x_1$ is sampled from $p(x_1|x_0)$; then the second value $x_2$ is sampled from $p(x_2|x_1)$ and so forth. For this purpose you need to be able to simulate from the conditional distributions $p(\cdot\vert\cdot)$. This is, you obtain a sample $\{x_i,i=1,...,N\}$

In the second sampling method (re-sampling) you already have a sample $\{x_i,i=1,...,N\}$ and you obtain a new sample by picking elements from the original one. This is similar to the 'urn game'. Imagine you have an urn with $N$ elements of different sizes (illustrating the different weights), you pick one of them, record the result and put it back in the urn. This experiment is repeated $M$ times.

I hope this helps.

Answer 2

Drawing a sample means sampling without replacement from a population. If you think of this like an urn with distinctly numbered balls in it, it means to take k and each time the urn has one less ball because the number you draw each time is not returned to the urn. Sampling with replacement means that each time the ball is returned to the urn. Hence when sampling with replacement you can get repeat numbers for the selected balls. When sampling with replacement each of the N balls has the same 1/N chance of being selected each time. When sampling without replacement the probability of being drawn changes based on the results of the preceding draws. Resampling is term used for a set of statistical techniques. With resampling you have an original sample drawn and then to make inferences about the population based on the sample you do addition sampling from the original sample. As an example the bootstrap is a resampling method. The ordinary bootstrap samples N times with replacement from an original sample of size N. Although resampling is usually done with equal weights it has been generalized to consider unequal weighting schemes. I am not sure what the original intent of your question was but if my interpretation is correct this description is missing from the other answer. The bootstrap was mentioned in one of the comments.

Answer 3

The practical difference between "sampling" and "sampling with replacement" is really in the accounting part of the probability weights, whether or not you can't have (or don't want) your whole data set in memory, and if sample ordering is important. If you wish to pursue it, Ordering is more related to "random-shuffling", which is out of context here. A dirth of information related to "sampling with replacement" is available in the context of "bootstrapping" and "online algorithms" are a standard remedy for memory constraints, which are also out of context here.

If you simply have $N$ observations, each will have an equal weighting (a uniform distribution) in a single random sample. So here "sampling with replacement" is equivalent to a repeated single random sampling. I typically generate a random index between $0$ and $N-1$, and select that index from my $N$ observations... then repeat $M$ times to get the specified sample size.

So we're all on the same page, you generate a random integer to use as an index as

              RandomIndex = (int)((max - min + 1) * RND + min)

where $RND$ is your favorite random number generator, returning a real number (decimal) between $0$ and $1$. Most often the standard function for your environment is sufficient, and here we use $0$ for the min and $N-1$ for the max.

However, you stated that you have frequency weights available for this problem, defined as $\{w_i; i=1,\dots,N\}$ in your notation; not too different really. We just need to tell our RandomIndex function to use a non-uniform distribution defined by your $\{w_i\}$. This puts a wrapper function around the $RND$ function. I typically use something cheap like

               Wtd.RND = function(weights[]) {
                         R = RND; index = 1; sum = weights[0];
                         while (sum ≤ R) {
                             sum += weights[index]; index++;}  
                         return index;
                         } 

Plug the wrapper function back in, and simplify some algebra, to get your new weighted index:

               WeightedIndex = (int)(N * Wtd.RND)

Now just select the weighted index from the $N$ observations... then repeat $M$ times to get the specified sample size.