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

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 ?

• Yes to both questions. For the first one, you need to be able to simulate from the conditional distribution, which is known. For the second one, you might be interested on the command R command sample in order to implement the re-sampling.
– user10525
Commented Jun 12, 2012 at 12:47
• @Procrastinator, that comment (with some more detail) has the makings of a nice answer, if you have time to give one Commented Jun 12, 2012 at 12:54
• @Procrastinator Well, I'm not using R, but I want to code that by my self in C++ or python. So for the first one, say that the conditional distribution is the standard gaussian distribution, are the generated samples $\tilde{x}_t^{(i)}$ some values in [0,1] (i.e. probabilities according to normal distribution), or they are any random values that can be generated according to a normal distribution ? For the second one, can you give a pseudo code algorithm to do this resampling of N values according to the weighted set of N values that we had ? Since I'm not using R. Thanks.
– shn
Commented Jun 12, 2012 at 13:11
• Actually, I believe you need to be careful in your terminology. You can sample from a set of data, both with and without replacement. You can also sample from a (parametric) distribution. I believe "re-sampling" is asociated with "bootstrapping", which might be a good place to look. Commented Jun 12, 2012 at 14:33
• @Wayne Yes, actually I was implementing a bootstrap filter, and what I was looking for in the second point was "re-sampling with replacement"
– shn
Commented Jun 12, 2012 at 14:42

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.

• Thanks, this is a great and complete answer. For the transition conditional distribution $p(x_t|x_{t-1})$, is it possible to define this model according to my own problem (for which I want to apply particle filter) instead of using some well known distributions such as $x_t \~ Normal(x_{t-1}, \sigma)$; or in most of cases we generally use some existing distributions (like uniform, normal, etc) ?
– shn
Commented Jun 12, 2012 at 15:45
• @user995434 The constrution of the conditional distribution is a completely different problem. This has to be done in such a way that the convergence to the objective distribution is ensured. It cannot be any distribution. Please, have a look a this link for some references.
– user10525
Commented Jun 12, 2012 at 16:11
• Well, so the construction of the conditional distribution according to a given problem, is also one of my concerns, and I have no idea about how to create a convenient conditional distribution. Should we think of this as a function which reflects how the estimated variable x is supposed to evolve over time ?
– shn
Commented Jun 12, 2012 at 16:38
• @user995434 Possibly but it is context-dependent. I think it would be a better idea that you expand your comment, giving a bit more of details of your context, in a new question. This is, explaining what is the goal of the simulation, what have you done, ...
– user10525
Commented Jun 12, 2012 at 16:41
• Ok, since it's context-dependent, I'll create later a new question about the construction of the conditional distribution in the context that I'm working on. I'll let you know when I do it. Thanks.
– shn
Commented Jun 12, 2012 at 16:46

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.

• I was in fact implementing the bootstrap filter. What is missing about the resampling in the previous answer ?!
– shn
Commented Jun 12, 2012 at 15:53
• @user995434 Procrastinator explained the concept of resampling but did not connect it to the inference techniques that are called resampling methods namely the bootstrap, subsampling, and permutation methods. Also with the bootstrap M is usually set equal to N. The only exceptions would be to use a smaller value for m because the ordinary bootstrap is inconsistent. Commented Jun 12, 2012 at 16:30
• I'm actually using M equal to N (fixed number of particles). What do you mean by "the ordinary bootstrap is inconsistent" ? Should I use another ameliorated bootstrap technique ? I'm actually using this algorithm
– shn
Commented Jun 12, 2012 at 16:43
• There are parameters that the ordinary bootstrap does not estimate correctly. One example estimation of the mean when the variance is infinite. Bickel and Ren showed that a so-called m out of n bootstrap can give the proper results as long as m goes to inifinty at a slower rate than n. This is covered in some detail in Chapter 9 "When Bootstrapping Fails Along with Some Remedies for Failures" of my book "Bootstrap Methods: A Guide for Practitioners and Researchers" Second Edition.(2007). Commented Jun 12, 2012 at 16:59
• Here is a link to where it is given on amazon: amazon.com/…. Commented Jun 12, 2012 at 16:59

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.

• Well, this a better algorithm than what I've implemented from the post of @Procrastonator, since it seems cheaper. By the way, "bootstrapping" and "online algorithms" are not out of context here, because I'm trying to use particle filters (e.g. bootstrap filter) for an online clustering problem.
– shn
Commented Jun 12, 2012 at 18:35