Introduction

Let's assume you want to share a pie with N people and the size of slices should be randomly drawn while making sure that nobody gets favoured. The size of slices can be interpreted as weights. Each weight need to between 0 and 1 while all the N weights need to sum up to 1 because we have unfortunately only one cake.

We are looking for a way to sample weights randomly were all N weights are identically distributed. The distribution of cake slices is the same for every of the N people who decided to share the cake.

Mathematically speaking, we look for a linear combination of N alternatives. If we have two options A₁ and A₂, we are looking for two weights w₁ and w₂ to obtain:

      f = w_1 * A_1 + w_2 * A_2

where w₁ is uniformly sampled between 0 and 1 and w₂ is set to (1-w₁).

With more options more complicated. As an example, we want to sample soil textures and have the three options (A₁) sand content, (A₂) silt, and (A₃) clay content. The weight of each option are w₁, w₂, and w₃. They need to sum up to 1. The order of weights should not matter, i.e. a high sand content should be as likely as a high clay or silt content. We hence want to uniformly sample from the sand-silt-clay classification diagram.

Naïve Sampling Strategy

A common strategy (references) is to sample the first weight w₁ ~ U[0,1]. Then sample the next weight in the remaining range w₂ ~ U[0,1-w₁]. The last weight is then set as the remainder w₃ = 1-w₁-w₂ to obtain a sum of 1. This naïve approach can be extended to any number N of alternatives and weights:

      w_1 ~ U[0,1]
      w_2 ~ U[0,1-w_1] 
      w_3 ~ U[0,1-w_1-w_2] 
      w_4 ~ U[0,1-w_1-w_2-w_3] 
      ...
      w_N = 1-w_1-w_2-...-w_(N-1)

The problem is that the distribution functions of the weights are not identical, leading to the fact that the order of the alternatives matters (large values of the first alternative/weight are always more likely than large weights of the last alternative). This can be seen in the histograms when three weights are sampled following this approach (Figure 1 Panels A-C). This in turn means for the soil texture example that the sand-silt-clay classification diagram is not sampled uniformly (Figure 1 Panel D).

Proposed Sampling Strategy

We hence propose the revised sampling strategy from the Pie Share Distribution to obtain N weights for N alternatives that are all identically distributed (see Figure 1 Panels E-G) leading to a uniform sampling of the full domain (See Figure 1 Panel H). The proposed transformation of (N-1) uniformly sampled random numbers r_i ~ U[0,1], i=1,..,(N-1) is as follows:

      w_1 ~ (1)            *(1-(1-r_1)**(1/(N-1)))
      w_2 ~ (1-w_1)        *(1-(1-r_2)**(1/(N-2)))
      w_3 ~ (1-w_1-w_2)    *(1-(1-r_3)**(1/(N-3)))
      w_4 ~ (1-w_1-w_2-w_3)*(1-(1-r_4)**(1/(N-4)))
      ...
      w_N = 1-w_1-w_2-...-w_(N-1)$

The N weights will be all identically distributed with the probability density function:

      _f(x) = N * (1-x)**(N-1)_.

Figure 1: The sampling of three weights w₁, w₂, and w₃ is shown for a naive approach (row 1) and the proposed strategy (row 2). The distribution of the three weights is not identical using the naive method (A-C) but yields the same distribution for the three weights when the proposed method is applied (E-G). The ternary diagrams (D and H) show that the domain is uniformly sampled only when the proposed method is applied. The naive method favoring small weights for weights w₂ and w₃ which leads to a more dense sampling close to the upper edge of the ternary diagram.