Skip to content

sampling

Classes for efficient random sampling from discrete distributions

VoseAliasSampling

Implementation of fast biased sampling of discrete values [0, ..., n]

For a concise explanation see https://www.keithschwarz.com/darts-dice-coins/

Parameters:

Name Type Description Default
weights typing.Union[numpy.array, list]

relative weights of the n events, where weights[i] is the relative statistical weight of event i. The weights do not need to be normalized.

For an array with length n, generated random values will be from range(n).

 required

Examples:

Create a VoseAliasSampling instance

>>> from pathpy.processes import VoseAliasSampling
>>> sampler = VoseAliasSampling([1,1,2])

Fast biased sampling in O(1)

>>> [ sampler.sample() for i in range(10) ]
[ 0 2 0 1 2 1 2 1 2 0 2 2 ]
Source code in src/pathpyG/processes/sampling.py 
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class VoseAliasSampling:
    """
    Implementation of fast biased sampling of discrete values [0, ..., n]

    For a concise explanation see https://www.keithschwarz.com/darts-dice-coins/

    Args:
        weights: relative weights of the n events, where weights[i] is the relative
            statistical weight of event i. The weights do not need to be
            normalized.

            For an array with length n, generated random values
            will be from range(n).

    Examples:
        Create a VoseAliasSampling instance

        >>> from pathpy.processes import VoseAliasSampling
        >>> sampler = VoseAliasSampling([1,1,2])

        Fast biased sampling in O(1)

        >>> [ sampler.sample() for i in range(10) ]
        [ 0 2 0 1 2 1 2 1 2 0 2 2 ]
    """

    def __init__(self, weights: Union[np.array, list]) -> None:
        """
        Initializes probability and alias tables
        """
        self.n = len(weights)
        self.probs = dict()
        self.scaled_probs = dict()
        self.aliases = dict()

        small = list()
        large = list()

        for i in range(1, self.n + 1):
            self.probs[i] = weights[i - 1]
            self.scaled_probs[i] = self.n * weights[i - 1]
            if self.scaled_probs[i] > 1:
                large.append(i)
            elif self.scaled_probs[i] <= 1:
                small.append(i)

        while small and large:
            l = small.pop()
            g = large.pop()

            self.probs[l] = self.scaled_probs[l]
            self.aliases[l] = g
            self.scaled_probs[g] = self.scaled_probs[l] + self.scaled_probs[g] - 1

            if self.scaled_probs[g] < 1:
                small.append(g)
            else:
                large.append(g)
        while large:
            g = large.pop()
            self.probs[g] = 1
        while small:
            l = small.pop()
            self.probs[l] = 1

    def sample(self) -> int:
        """
        Biased sampling of discrete value in O(1)

        Returns: integer value from range(n), where n is the length
            of the weight array used to create the instance.
        """
        i = np.random.randint(1, self.n + 1)
        x = np.random.rand()
        if x < self.probs[i]:
            return i - 1
        else:
            return self.aliases[i] - 1

__init__

Initializes probability and alias tables

Source code in src/pathpyG/processes/sampling.py 
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def __init__(self, weights: Union[np.array, list]) -> None:
    """
    Initializes probability and alias tables
    """
    self.n = len(weights)
    self.probs = dict()
    self.scaled_probs = dict()
    self.aliases = dict()

    small = list()
    large = list()

    for i in range(1, self.n + 1):
        self.probs[i] = weights[i - 1]
        self.scaled_probs[i] = self.n * weights[i - 1]
        if self.scaled_probs[i] > 1:
            large.append(i)
        elif self.scaled_probs[i] <= 1:
            small.append(i)

    while small and large:
        l = small.pop()
        g = large.pop()

        self.probs[l] = self.scaled_probs[l]
        self.aliases[l] = g
        self.scaled_probs[g] = self.scaled_probs[l] + self.scaled_probs[g] - 1

        if self.scaled_probs[g] < 1:
            small.append(g)
        else:
            large.append(g)
    while large:
        g = large.pop()
        self.probs[g] = 1
    while small:
        l = small.pop()
        self.probs[l] = 1

sample

Biased sampling of discrete value in O(1)

integer value from range(n), where n is the length

Type Description
int

of the weight array used to create the instance.
Source code in src/pathpyG/processes/sampling.py 
84
85
86
87
88
89
90
91
92
93
94
95
96
def sample(self) -> int:
    """
    Biased sampling of discrete value in O(1)

    Returns: integer value from range(n), where n is the length
        of the weight array used to create the instance.
    """
    i = np.random.randint(1, self.n + 1)
    x = np.random.rand()
    if x < self.probs[i]:
        return i - 1
    else:
        return self.aliases[i] - 1