# Understanding Bayesian Bootstrap theory

I'm trying to understand the theory in section 4 of Rubin (1981) paper on Bayesian Bootstrap (BB):

$$\textbf{Theory:}$$ Let $$d=\left(d_{1}, \ldots, d_{K}\right)$$ be the vector of all possible distinct values of $$X$$, and let $$\pi=\left(\pi_{1}, \cdots, \pi_{K}\right)$$ be the associated vector of probabilities $$P\left(X=d_{k} \mid \pi\right)=\pi_{k}, \quad \sum \pi_{k}=1$$ Let $$x_{1}, \ldots, x_{n}$$ be an i.i.d. sample from the equation above and let $$n_{k}$$ be the number of $$x_{i}$$ equal to $$d_{k}$$. If the prior distribution of $$\pi$$ is proportional to $$\prod_{k=1}^{K}\pi_{k}^{l_k}\quad \left(0\right. \text { if } \left.\sum\pi_{k} \neq 1\right)$$ then the posterior distribution of $$\pi$$ is the $$K-1$$ variate Dirichlet distribution $$D\left(n_{1}+l_{1}+1,\right.$$ $$\left.\ldots, n_{K}+l_{K}+1\right)$$ which is proportional to $$\quad \prod_{k=1}^{K} \pi_{k}^{\left(n_{k}+l_{k}\right)} \quad\left(0\right. \text{ if } x_{\imath} \neq d_{k} \text{for some } i, k \text{ or if} \left.\sum \pi_{k} \neq 1\right)$$

• What does $$K-1$$ variate mean?

This posterior distribution can be simulated using $$m-1$$ independent uniform random numbers, where $$m=n+K+\sum_{1}^{K} l_{k}$$.

• Where does this come from?

Let $$u_{1}, \cdots, u_{m-1}$$ be i.i.d. $$U(0,1),$$ and let $$g_{1}, \cdots, g_{m}$$ be the $$m$$ gaps generated by the ordered $$u_{\imath}$$. Partition the $$g_{1}, \cdots, g_{m}$$ into $$K$$ collections, the $$k$$-th having $$n_{k}+l_{k}+1$$ elements,

• Is element referring to $$u$$'s or gaps? I think gaps because $$\sum_1^K(n_{k}+l_{k}+1)=m$$. If so, is partitioning mean to group adjacent gaps together? Something like the bottom line below for $$m=7$$ and $$K=3$$?

and let $$P_{k}$$ be the sum of the $$g_{i}$$ in the $$k$$-th collection, $$k=1, \cdots, K$$.

• Does this mean $$P_{k}$$ is the size of collection $$k$$? Does "sum of the $$g_{i}$$" mean sum of the length of $$g_{i}$$'s?

Then $$\left(P_{1}, \ldots, P_{K}\right)$$ follows the $$K-1$$ variate $$D\left(n_{1}+l_{1}+1, \ldots, n_{K}+l_{K}+1\right)$$ distribution. Consequently, the BB which assigns one gap to each $$x_{i}$$

• But we have $$m$$ gaps vs. $$n$$ $$x_i$$'s. How does this work?

is simulating

• What does simulating mean in this context?

the posterior distribution of $$\pi$$ and thus of a parameter $$\phi=\Phi(\pi, d)$$ under the improper prior distribution proportional to $$\prod_{k=1}^{K} \pi_{k}^{-1}$$.

• Where did the $$l_k=-1$$ come from?

Simulations corresponding to other prior distributions with integer $$l_{k}$$ can also be performed; for example, with a uniform prior distribution on $$\pi$$, (i.e., all $$l_{k}=0$$ ) generate $$n+K-1$$ uniform random variables, form $$n+K$$ gaps, add the first $$\left(n_{1}+1\right)$$ gaps together to yield the simulated value of $$\pi_{1}$$, add the second $$\left(n_{2}+1\right)$$ gaps together to yield the simulated value of $$\pi_{2}$$, and so on. However, when using a proper prior distribution, all a priori possible values of $$X$$ must be specified because they have positive posterior probability.

• What does "all a priori possible values of $$X$$ must be specified" mean and how is this different from the previous case of improper prior with $$l_k=-1$$?

The $$(K-1)$$-variate Dirichlet distribution: What Rubin means here is that the Dirichlet distribution is giving a random probability vector $$\boldsymbol{\pi} = (\pi_1,...,\pi_K)$$ with $$K$$ elements, so only $$K-1$$ of these elements are "free variables". Since the probability values must sum to one you have the binding equation $$\pi_K = 1-\sum_{k=1}^{K-1} \pi_k$$ on the last element. It is therefore a matter of convention/framing whether you include this last element as part of the argument of the distribution or exclude it and treat it as a separate equation for a value outside the distribution argument. Rubin is using the convention of regarding this element to be excluded from the argument, and so he refers to this as the "$$K-1$$-variate" version of the distribution; that is the number of free variables in the argument of the density.

It is worth noting here that there is some variation in how statisticians and other analysts refer to the Dirichlet distribution, often depending on context. Sometimes we find it easier to include the final element in the argument and think of this as the $$K$$-variate case; we then consider the distribution to have an equation constraint on its argument values. Alernatively, sometimes we prefer to exclude the final element from the argument and think of this as a $$(K-1)$$-variate case; we then consider the distribution to have an inequality constraint on its argument values. This is summarised in the two approaches below:

$$\begin{matrix} \text{Approach} & & \text{Argument} & & \text{Constraints/Definitions} \\[6pt] (K-1) \text{-variate} & & \ \boldsymbol{\pi}_* \equiv (\pi_1,...,\pi_{K-1}) & & \sum_{k=1}^{K-1} \pi_k \leqslant 1, \pi_K \equiv 1-\sum_{k=1}^{K-1} \pi_k, \\[6pt] K \text{-variate} & & \boldsymbol{\pi} \equiv (\pi_1,...,\pi_K) & & \sum_{k=1}^{K} \pi_k = 1 . \\[6pt] \end{matrix}$$

The main advantage of the first approach is that the beta distribution corresponds to the univariate case, which is a fairly natural way to look at it. If we use the second approach then even modelling the distribution of a single probability must be expressed by the pair $$(\pi,1-\pi)$$, and this is less parsimonious than is desirable.

So, Rubin is calling this the $$(K-1)$$-variate version of the distribution because he is looking at the number of free parameters in the argument. In any case, don't let this issue confuse you --- regardless of what he calls it, Rubin gives an explicit formula for the density kernel, which is enough to understand the problem without ambiguity.

In fact, in the present context, it is simpler to frame the distribution with all $$K$$ probability values in the argument of the density function. This would give the explicit density kernel:

$$\text{Dirichlet}(\boldsymbol{\pi}|\mathbf{n}+\mathbf{l}+1) \propto \mathbb{I}(\boldsymbol{\pi} \in \boldsymbol{\Pi}_K) \prod_{k=1}^K \pi_k^{n_k + l_k},$$

where $$\boldsymbol{\Pi}_K \equiv \{ \boldsymbol{\pi} \in \mathbb{R}^K | \sum_k \pi_k = 1, \pi_k \geqslant 0 \}$$ is the space of all possible probability vectors of length $$K$$ (i.e., the probability simplex).

Generating the Dirichlet distribution using uniform random variables: To assist you to understand this part, I will set out the method Rubin is describing using some explicit formulae that he only describes in words. This is a method that is used to generate Dirichlet random vectors from an underlying set of IID uniform random variables in the special case when the parameter of the Dirichlet distribution is a vector of integers. You start by generating $$u_1,...,u_{m-1} \sim \text{IID U}(0,1)$$ and then you form the 'gaps' $$g_1,...,g_m$$ defined by:

$$g_k \equiv u_k-u_{k-1} \quad \quad \quad (u_0 \equiv 0, u_m \equiv 1).$$

Before proceeding, note here that we have $$K$$ gap values and these must sum to one ---i.e., we have $$\sum_i g_i = 1$$. Rubin then describes the idea that you partition the gap values so that there are $$n_k+l_k+1$$ values in the $$k$$th partition piece. He does not mention any further restriction on the partition, so presumably any partition that meets this criterion is acceptable. (The partition you mention, grouping adjacent gaps together, would be a legitimate partition that meets the requirement, but not the only one.)

Let's follow Rubin's description but put it in explicit terms. The easiest way to do this is to denote the partition of the indices $$1,...,m$$ by the $$\mathscr{P} = \{ \mathcal{P}_1,...,\mathcal{P}_K \}$$. Note that each partition set $$\mathcal{P}_k$$ has $$n_k+l_k+1$$ elements in it (and is disjoint from the other partition sets since this is a partition). We can then write the resulting sum quantities as:

$$P_k \equiv \sum_{i \in \mathcal{P}_k} g_i \quad \quad \quad \text{for } k = 1,...,K.$$

Note here that these are sums of gap values (not the initial uniform random variables) taken over the partition sets. So in answer to your question on this part, yes, these are sums of the lengths of the gaps. Now, recall from our above definitions that we must have $$\sum g_i = 1$$. Rubin asserts that the random vector we have formed has the required Dirichlet distribution:

$$(P_1,...,P_K) \sim \text{Dirichlet}(\mathbf{n}+\mathbf{l}).$$

I note your confusion that we have $$n$$ data points and $$m$$ gaps, but we get a result for $$K$$ elements here. Remember that we are here forming the posterior distribution, which is for a random vector with $$K$$ elements. The $$n$$ data points only come into this as part of the Dirichlet parameter, and has no further relevance. As to the $$m$$ gaps, these were formed initially to correspond with the sum of the elements of the Dirichlet parameter, but we then summed the gaps to get a final vector with $$K$$ elements.

In terms of where this result comes from, I don't have a reference on hand, but it is an extension of an older method for generating uniform random vectors on a probability simplex. The present method extends that older result by allowing you to generate random vectors on the probability simplex that follow a Dirichlet distribution with integer parameters. If you look up literature on the Dirichlet distribution then I'm sure you will be able to find some references that trace this method back to its original literature.

Special case: Rubin makes some observations on simulation of the "improper" Dirichlet prior. What he is saying here is that if you set $$\mathbf{n} = \mathbf{l} = \mathbf{0}$$ then you end up generating $$m=K$$ uniform values in this method. Substituting $$\mathbf{n} = \mathbf{l} = \mathbf{0}$$ you will see that this particular case corresponds with simulating a probability vector from the improper Dirichlet distribution:

$$(P_1,...,P_K) \sim \text{Dirichlet}(\mathbf{0}) \propto \mathbb{I}(\boldsymbol{\pi} \in \boldsymbol{\Pi}_K) \prod_{k=1}^K \pi_k^{-1}.$$

This is one particular case that can be simulated with the method, but Rubin notes that you can simulate any Dirichlet distribution with integer parameters. (I am not certain what he means when he refers to the requirement to specify all possible a priori values of the data. Perhaps he means that it is desirable to generate an algorithm for this method that allows any valid data input.)

Your remaining questions concern the merits of using different types of Dirichlet distributions (e.g., the improper version versus the uniform version, etc.). There is no sacrosanct answer here except to note that context and theory will determine what is the appropriate parameter to use. In Bayesian analysis it is common to use a "non-informative" prior which sets $$\mathbf{l} = \mathbf{1}$$ to give a uniform prior over the set of all possible probability vectors. There are other suggestions for alternative priors, such as Jeffrey's prior (but note that this does not use integer parameters so it is not amenable to the present method).

You are correct that it is usually considered "more sensible" to use the flat Dirichlet prior than the improper prior. (Although I should hedge this by saying that this is judgment usually made by "objective" Bayesians; subjective Bayesians would say it is arbitrary what prior you use.) You also ask about the considerations when using a flat prior. The main advantages of this prior are that it falls within the conjugate form (i.e., it is a Dirichlet distribution) and it also has a plausible claim to being "non-informative" in a fairly intuitive sense.

Remember that Bayesian analysis has well-established theorems relating to posterior consistency, and broadly speaking, these theorems say that different priors still lead to convergence of posterior beliefs (under very weak conditions) as we get more and more data. For this reason, agonising over small differences in the prior is arguably a kind of statistician navel-gazing; that effort is much better spent trying to get more data.

• Great answer! My impression from reading Rubin is also that he surely does not advocate this particular prior, but rather points out that this prior is closely related to what a frequentist bootstrap implicitly uses, and hence that a frequentist bootstrapper so to speak adopts this prior that most people find unreasonable, as it basically just puts weight on (in the Bernoulli case) zero and unit success probability? – Christoph Hanck Aug 21 '20 at 6:43