## Introduction

This article was conceived during my attempt at figuring out which bootstrap method do I need to use in my work. It turned out that the majority of source material is quite dense and hard to get through.

I will try to mitigate the situation by providing straightforward explanations and intuitive pictures for some established variations of the bootstrap method so that a person can understand what’s going on first and select which method might be useful for them. Also, I’ll provide links to the original articles that first proposed each method, as well as articles and books that analyze and compare them. A couple of ready-to-use implementations will be provided as well.

The goal is to make this article a starting point for people that need to use bootstrap as a method but remain unsure of which options are available to them and how to make a definitive choice.

### Disclaimer

I am not a trained statistician and I do not specialize in applied math and statistics. I am a programmer and machine learning specialist by trade, so take everything I say with a pinch of salt and re-verify.

### TL;DR

Use original IID Boostrap if your data is independently and identically distributed.

Implementations: numpy, sklearn, recombinator.

For numpy and sklearn, set `replace = True`

.

Use Stationary Bootstrap with optimal block size if your data has serial dependence.

Implementations: method, block size.

## What is bootstrap

Bootstrap is one of the methods of resampling data, and two characteristics can be used to classify a sampling method as bootstrap.

- Sampling is done with replacement
- The number of observations sampled equals the number of original observations.

## Variations of the bootstrap method

There are many proposed variations of the bootstrap method. Here is a rough categorization of some of them:

- Single-point IID bootstrap (IIDB)
- Block bootstrap methods
- Other variations

### Single-point IID Bootstrap (IIDB)

Originally proposed in Efron (1979).

For proper mathematical treatment, read Chapter 2.2 in Lahiri (2003).

The data is sampled with replacement, a single element at a time. The number of draws is typically the same as the number of elements in the dataset. The process is repeated multiple times.

Typical parameters:

`sample_size = n = dataset_size`

`n_samples = hundreds to thousands`

**Example:** Randomly draw an element 20 times from the dataset of 20 items. The sampled element is not removed after the draw and therefore, can occur more than once among the resulting 20 elements.

### Non-overlapping Block Bootstrap (NBB)

Originally proposed in Carlstein (1986).

For proper mathematical treatment, read Chapter 2.6 in Lahiri (2003).

The idea behind block bootstraps stems from a shortcoming of the original IID bootstrap. It assumes that the observations in a dataset are independently and identically distributed (i.i.d.). This is mostly true for problems that allowed the original bootstrap to attain widespread adoption. However, for many other problems, the assumption does not hold.

Block bootstrap authors all zeroed in on a similar solution: sample blocks of consecutive elements instead of single observations.

The difference between NBB and other block bootstraps is that in NBB, blocks are all the same length, can not overlap (share the same elements), and their position is predefined and stays constant during the entire bootstrap process.

Typical parameters:

`block_size = from n^(1/5) to n^(1/2)`

`n_blocks = n / block_size`

**Example:** Separate the datasets into blocks of a fixed length of 2. Draw 10 blocks with replacement. Merge the blocks into the resulting dataset in the order they were drawn without re-ordering.

### Ordered Non-overlapping Block Bootstrap (ONBB)

Originally proposed in Beyaztas et al. (2016). Its performance was also discussed in Beyaztas and Firuzan (2016).

The next three modifications of NBB were proposed by the same group of authors in the same article. They claim that the variations are:

good competitors that often exhibit improved performance over the conventional block methods.

The difference between Ordered NBB and NBB is that the blocks are sorted in ascending order after all blocks are drawn but before they are merged into the resulting sample.

**Example:** Separate the dataset into blocks of a fixed length of 2. Draw 10 blocks with replacement and sort blocks in ascending order. Merge blocks into the resulting dataset.

### Sufficient Non-overlapping Block Bootstrap (SNBB)

Originally proposed in Beyaztas et al. (2016). Its performance was also discussed in Beyaztas and Firuzan (2016).

The difference between Sufficient NBB and NBB is that repeated blocks are discarded after all blocks are drawn.

**Example:** Separate the dataset into blocks of a fixed length of 2. Draw 10 blocks with replacement. Discard repeating blocks. Merge blocks into the resulting dataset in the order they were drawn without re-ordering.

### Sufficient Ordered Non-overlapping Block Bootstrap (SONBB)

Originally proposed in Beyaztas et al. (2016). Its performance was also discussed in Beyaztas and Firuzan (2016).

The difference between Sufficient Ordered NBB and NBB is that after drawing all the blocks, repeated blocks are discarded. Afterward, the remaining blocks are sorted in ascending order before they are merged into the resulting sample.

**Example:** Separate the dataset into blocks of a fixed length of 2. Draw 10 blocks with replacement. Discard repeating blocks and sort blocks in ascending order. Merge blocks into the resulting dataset.

### Moving Block Bootstrap (MBB)

Originally proposed in Künsch (1989).

For proper mathematical treatment, read Chapter 2.5 in Lahiri (2003).

Moving Block Bootstrap started another branch of bootstrap methods. Its main difference from NBB is that block positions are not predefined, and blocks can overlap.

Typical parameters:

`block_size = from n^(1/5) to n^(1/2)`

`n_blocks = n / block_size`

**Example:** Draw 5 blocks of consecutive elements with replacement. Blocks can start at any element and can overlap. Merge blocks into the resulting dataset in the order they were drawn without re-ordering.

### Circular Block Bootstrap (CBB)

Originally proposed in Politis and Romano (1992a) and Politis and Romano (1992b).

For proper mathematical treatment, read Chapter 2.7.1 in Lahiri (2003).

It was found that the MBB method has a problem. Because of fixed block sizes, the edges of datasets are systematically undersampled. This leads to a skewed distribution of the resulting observations where the mean of the original dataset is not the same as the mean of bootstrapped datasets.

Circular Block Bootstrap resolves this issue by “wrapping dataset around in a circle,” thus allowing blocks to span from the end to the beginning of the dataset, equally sampling all observations.

Typical parameters:

`block_size = from n^(1/5) to n^(1/2)`

`n_blocks = n / block_size`

**Example:** Draw 5 blocks of consecutive elements with replacement. Blocks can start at any element and can overlap. Blocks can also start at the end of the dataset and continue to the start. Merge the blocks into the resulting dataset in the order they were drawn without re-ordering.

### Stationary Block Bootstrap (SBB)

Originally proposed in Politis and Romano (1994)

For proper mathematical treatment, read Chapter 2.7.2 in Lahiri (2003).

The next modification of the MBB is from the same authors, and it solves another issue that the method has. Even when the input dataset is stationary, the sample produced by MBB lacks stationarity.

Stationary Block Bootstrap solves this problem by using randomized block sizes instead of static blocks like all previous variations did. Block sizes in SBB are distributed geometrically around the selected mean.

Typical parameters:

`mean_block_size = from n^(1/5) to n^(1/2)`

`output_size = n`

**Example:** Draw random blocks of consecutive elements with replacement. Continue until 20 elements are sampled. Blocks can start at any element and can overlap. Block size is random and varies geometrically around mean_block_size. Merge blocks into the resulting dataset in the order they were drawn without re-ordering.

### Hybrid Block Bootstrap (HBB)

Originally proposed in Kuffner et al. (2018)

Another interesting modification of block bootstrap, the HBB proposes to sample less than **n / block_size **blocks each iteration, and it provides a procedure to select the optimal number of blocks and block size for a specific dataset.

Typical parameters:

`block_size = from n^(1/5) to n^(1/2)`

`n_blocks = 0.1 … 0.2 * n / block_size`

**Example:** Draw 3 blocks of consecutive elements with replacement. Blocks can start at any element and can overlap. Merge blocks into the resulting dataset in the order they were drawn without re-ordering. The resulting sample size is typically less than the original dataset size.

### Other variations

There are many more variations of bootstraps available. Since there are limits to what can be described in one article and what can be visualized intuitively in one picture, I will provide only links for the following methods:

## Which variation to choose

The correct way to choose would be to understand the kind of problem you are trying to solve and the properties that your data exhibits. Afterward, read the article along with the comparisons to decide how good a fit a specific variation is for the problem you want to solve.

However, here are some rules to keep in mind:

- If your data is i.i.d., then the original IID bootstrap is sufficient and nothing else may be necessary.
- If your data has serial dependence, using one of the block bootstraps is the way to go. Among block bootstraps, Stationary Bootstrap seems to solve most of the problems of the other variations. It also has procedures to select optimal block sizes.
- If you have more specific needs, then you’ll need to dive in and conduct more exhaustive research.

## Implementations

Here are several packages that implement the algorithms described above.

If you need IID bootstrap, you can just use sklearn’s resample with replace=True. Otherwise, I strongly recommend that you take a look at recombinator. It implements IIDB, MBB, CBB, SBB and others, as well as providing a lot of convenience tools for estimating optimal block sizes, conducting statistical tests, and so on. It’s a very underrated package.

### Python

### R

## Conclusion

The article turned out to be quite a long read. Nevertheless, I hope it made things clearer for you. I tried my best to verify what I say and correctly represent the workings of each method visually, but there is always room for mistakes. Let me know if you spot any, and I will fix them and update the article.

## Leave a Reply