L = len(Prob_val)
    # Initialize two arrays
    accept_prob = np.zeros(L)   # Saved probability
    alias_index = np.zeros(L, dtype=np.int)  # Save the subscript / serial number

    # Large queues are used to store node labels with an area larger than 1, and small queues are used to store node labels with an area smaller than 1.
    small_queue = []
    large_queue = []

    for index, prob in enumerate(Prob_val):
        accept_prob[index] = L*prob

        if accept_prob[index] < 1.0:
            small_queue.append(index)
        else:
            large_queue.append(index)

    # 1. Take one from each of the two queues at a time, and let the big one supplement the small one, and then the small one out of the small queue
    # 2. After looking at the big value and subtracting the small supply, the remaining value, if it is greater than 1, continue to be placed in the large queue; if it is exactly equal to 1, it will be out of the queue; if it is less than 1, join the small queue
    while small_queue and large_queue:
        small_index = small_queue.pop()
        large_index = large_queue.pop()
        # Because there is stored in alias_index: the label of another event, then now with a large probability to supplement the small probability, the label will become the label of the large event
        alias_index[small_index] = large_index
        # The principle of supplementation is: the large probability is to fill up the small probability (to the probability of 1), then the rest
        accept_prob[large_index] = accept_prob[large_index] + accept_prob[small_index] - 1.0
        # After judging the completion, the size of the remaining value
        if accept_prob[large_index] < 1.0:
            small_queue.append(large_index)
        else:
            large_queue.append(large_index)

return accept_prob, alias_index

def alias_smaple(accept_prob, alias_index):
    N = len(accept_prob)

    # Throw the first dice to generate the first random number from 1 to N, and decide which column to fall in
    random_num1 = int(np.floor(np.random.rand()*N))
    # Throw the second dice, generate a random number between 0 ~ 1, judge the size of accept_prob [random_num1]
    random_num2 = np.random.rand()

    # If less than Prab [i], sample i, if greater than Prab [i], sample Alias ​​[i]
    if random_num2 < accept_prob[random_num1]:
        return random_num1
    else:
        alias_index[random_num1]

import numpy as np
from numba import njit


@njit(nogil=True)
def random_walk(walk_length, p, q, t):
    """sample a random walk starting from t
    """
    # Normalize the weights to compute rejection probabilities
    max_prob = max(1 / p, 1, 1 / q)
    prob_0 = 1 / p / max_prob
    prob_1 = 1 / max_prob
    prob_2 = 1 / q / max_prob

    # Initialize the walk
    walk = np.empty(walk_length, dtype=indices.dtype)
    walk[0] = t
    walk[1] = random_neighbor(t)

    for j in range(2, walk_length):
        while True:
            new_node = random_neighbor(walk[j - 1])
            r = np.random.rand()
            if new_node == walk[j - 2]:
                # back to the previous node
                if r < prob_0:
                    break
            elif is_neighbor(walk[j - 2], new_node):
                # distance 1
                if r < prob_1:
                    break
            elif r < prob_2:
                # distance 2
                break
        walk[j] = new_node
        
    return walk

    walk[0] = t
    walk[1] = random_neighbor(t)

    for j in range(2, walk_length):
        while True:
            new_node = random_neighbor(walk[j - 1])
            r = np.random.rand()
            if new_node == walk[j - 2]:
                # back to the previous node
                if r < prob_0:
                    break
            elif is_neighbor(walk[j - 2], new_node):
                # distance 1
                if r < prob_1:
                    break
            elif r < prob_2:
                # distance 2
                break
        walk[j] = new_node