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 be 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 with all N weights being identically distributed. Means we want the distribution of cake slices to be the same for each 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:

      A = 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 it is more complicated. As an example, we want to sample soil textures. We therefore have the three options (A₁) sand content, (A₂) silt, and (A₃) clay content. The weight for each option is w₁, w₂, and w₃, respectively. The weights need to sum up to 1. The soil texture is then:

      texture = w_1 * A_1 + w_2 * A_2 + w_3 * A_3

The order of weights should not matter, i.e. a high sand content should be as likely as a high clay or silt content. This means we want to uniformly sample from the sand-silt-clay classification diagram.

Naïve Sampling Strategy

One strategy could be 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 are 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.