Aliasing construction

To use Walker's algorithm, as described in [Wal74] and [Sch83], to simulate transitions of Markov chains, we must build aliasing arrays.
Consider a construction example, issued from [Mor02].

Example 2 (Aliasing precomputation)   Let $X$ a random variable defined on the space states $\dco 0..5\dcf$ by the probability distribution $p=(p_i)_{0\leq i \leq 5}$ :

$$p=(0.1,0.3,0.2,0.1,0.2,0.1)$$

At the start of computation, we have respectively, "low" and "high" set :

$$L=\{0,3,5\}$$

and

$$H=\{1,2,4\}$$

Figure 1.1: Aliasing construction : initial step.

Figure 1.2: Aliasing construction : first step.

$$R[1]=R[1]+R[0]-1=1.8+0.6-1=1.4$$

$$A[0]=1$$

$L=\{0,3,5\}$ et $H=\{1,2,4\}$.

Figure 1.3: Aliasing construction : second step.

$$R[1]=R[1]+R[3]-1=1.0$$

$$A[3]=1 \rightarrow L=\{0,1,3,5\},\;H=\{2,4\}.$$

Figure 1.4: Aliasing construction : third step.

$$R[2]=R[2]+R[5]-1=0.8$$

$$A[5]=2$$

$L=\{0,1,2,3,5\}$ et $H=\{4\}$.

Figure 1.5: Aliasing construction : final step.

$$R[4]=R[4]+R[2]-1=1.0$$

$$A[2]=4$$

$L=\{0,1,2,3,4,5\}$ et $H=\emptyset$

Figure 1.6: Aliasing construction : end of construction.

It follows this (non unique) Aliasing construction :

States	0	1	2	3	4	5
Thresholds	0.6	1.0	0.8	0.6	1.0	0.6
Alias	1	/	4	1	/	2