Индекс $i$ можно определять непосредственно просмотром $s_i$ подряд. Если $k$ велико, можно применять специальные приёмы ускоренного поиска, например, деление множества индексов примерно пополам.
Самую эффективную схему предложил в 1977 г. А. Уолкер.
==Схема Уолкера==
Если бы все исходы имели одинаковые вероятности, моделировать такое распределение было бы очень просто. В такой ситуации достаточно разделить отрезок $[0, 1]$ на $k$ одинаковых частей, соответствующих этим исходам, и определить, в какую часть отрезка попало значение случайного датчика $x$. А это выясняется очень просто: нужно взять целую часть произведения $k \cdot x$. Так
что при исходах 0, 1, 2, 3 значению $x = 0.333$ соответствует исход $1$,
поскольку $4x = 1.332$.
Можно "подгонять" распределение под равномерное, передавая часть "вероятностной массы" от одних исходов другим. Если четыре исхода должны иметь вероятности, те же четыре исхода должны иметь вероятности, соответственно, $0.25$, $0.31$, $0.19$ и $0.25$, то исход $2$, получая, как все другие, долю $0.25$ и нуждаясь в доле $0.19$, может быть своеобразным "донором" и отдать исходу $1$, нуждающемуся в доле $0.31$, свои лишние шесть сотых. Эта передача воплощается в следующих действиях при генерировании случайного исхода: берется случайное число, например можможно использовать непосредственно дробную часть числа $k \cdot x$, и если это число меньше чем $0.19 \cdot 4 = 0.76$, то результатом будет исход $2$, а если больше, то исход $1$ (здесь случай равенства несуществен, его можно приписать к любой альтернативе). Эта передача обеспечит нужное увеличение доли для исхода $1$ и уменьшение $-$ для исхода $2$. Исход $1$ служит здесь "реципиентом" для "донора", исхода $2$.
Такую передачу "вероятностной массы" можно проводить в каждом диапазоне, причем если "владельцами диапазонов" удобно назначать различные исходы, то реципиентами разных диапазонов могут быть одни и те же исходы. Например, взяв ту же схему с четырьмя исходами, назначим реципиентом при исходе $0$ исход $3$ с долей $0.07$, при
исходе $1$ $-$ исход $2$ с долей $0.11$, при исходе $2$ $-$ исход $3$ с долей $0.14$,
наконец, при исходе $3$ $-$ исход $1$ с долей $0$. Подсчитаем окончательную вероятность получения каждого исхода:
<center>
$p_0 = 0.25- 0.07 = 0.18$,
$p_1 = 0.25 - 0.11 + 0 = 0.14$,
$p_2 = 0.25 - 0.14 + 0.11 = 0.22$,
$p_3 = 0.25 + 0.07 + 0.14 = 0.46$.
</center>
А создание по этой схеме очередного значения будет таким же простым, как и раньше: только в каждом диапазоне нужно будет решать, какой выбирать исход, основной или дополнительный. Сложность розыгрыша не зависит от количества исходов.
Такую схему можно создать для любого распределения вероятностей, причем у каждого исхода-донора будет только один исход-реципиент. Схема создается последовательно. На каждом шаге выбирается донор, не полностью использующий свою долю, и реципиент, которому требуется добавка. Конечно, после каждой передачи нужно исключить из рассмотрения донора и уменьшить долю реципиента, так что на следующих итерациях он может сам стать донором.
Пример: Возьмем распределение $p_A = 0.07$, $p_B = 0.31$, $p_C = 0.35$ и $p_D = 0.27$. Для него мы можем получить:
<center>
{| class="wikitable"
|-
! Донор !! Барьер !! Реципиент !! Остаток у реципиента
|-
| A || $0.07 \cdot 4$ || B || $0.31 - 0.18 = 0.13$
|-
| B || $0.13 \cdot 4$ || D || $0.27 - 0.12 = 0.15$
|-
| D || $0.15 \cdot 4$ || C || $0.35 - 0.10 = 0.25$
|-
| C || $0.25 \cdot 4$ || A || $0$
|}
</center>
При моделировании эти числа используются так: разыгрывается случайное число $x \in [0, 1]$, пусть получилось $x = 0.531$. Это число умножается на $k$: $0.531 \times 4 = 2.124$. Целая часть произведения определяет строку таблицы, считая от нуля, значит, третью сверху строку с основным исходом $D$ и дополнительным $C$. Дробная часть произведения $0.124$ сравнивается с барьером $0.6$, и так как барьер выше, то принимается основной исход.
==Общий случай==
