Английская Википедия:Alias method

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description

A circle on the left has 5 lines to 5 boxes in a column labeled "Acceptance". The first and second box are solid and each have the number 1 in them. The second box is half full and has the number 0.5 in it. The fourth box is solid with a 1 and the fifth box is three quarters full with a 0.75. Each box has an arrow from the filled region to its index, i.e., the first box points to a 1, the second box to a two, etc. There is a second column of five boxes labeled "Alias", each corresponding to one of the first boxes. Three are empty, but the third has a 2 in it and the fifth has a 1 in it. There is an arrow from the empty part of the third box in the first column to the third box in the second column and similarly for the fifth boxes.
A diagram of an alias table that represents the probability distribution〈0.25, 0.3, 0.1, 0.2, 0.15〉

In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, published in 1974 by A. J. Walker.[1][2] That is, it returns integer values Шаблон:Math according to some arbitrary probability distribution Шаблон:Mvar. The algorithms typically use Шаблон:Math or Шаблон:Math preprocessing time, after which random values can be drawn from the distribution in Шаблон:Math time.[3]

Operation

Internally, the algorithm consults two tables, a probability table Шаблон:Mvar and an alias table Шаблон:Mvar (for Шаблон:Math). To generate a random outcome, a fair dice is rolled to determine an index into the two tables. Based on the probability stored at that index, a biased coin is then flipped, and the outcome of the flip is used to choose between a result of Шаблон:Mvar and Шаблон:Mvar.[4]

More concretely, the algorithm operates as follows:

  1. Generate a uniform random variate Шаблон:Math.
  2. Let Шаблон:Math and Шаблон:Math. (This makes Шаблон:Math uniformly distributed on Шаблон:Math and Шаблон:Math uniformly distributed on Шаблон:Math.)
  3. If Шаблон:Math, return Шаблон:Mvar. This is the biased coin flip.
  4. Otherwise, return Шаблон:Mvar.

An alternative formulation of the probability table, proposed by Marsaglia et al.[5] as the "square histogram" method, uses the condition Шаблон:Math in the third step (where Шаблон:Math) instead of computing Шаблон:Mvar.

Table generation

The distribution may be padded with additional probabilities Шаблон:Math to increase Шаблон:Mvar to a convenient value, such as a power of two.

To generate the table, first initialize Шаблон:Math. While doing this, divide the table entries into three categories:

If Шаблон:Math, the corresponding value Шаблон:Mvar will never be consulted and is unimportant, but a value of Шаблон:Math is sensible.

As long as not all table entries are exactly full, repeat the following steps:

  1. Arbitrarily choose an overfull entry Шаблон:Math and an underfull entry Шаблон:Math. (If one of these exists, the other must, as well.)
  2. Allocate the unused space in entry Шаблон:Mvar to outcome Шаблон:Mvar, by setting Шаблон:Math.
  3. Remove the allocated space from entry Шаблон:Mvar by changing Шаблон:Math.
  4. Entry Шаблон:Mvar is now exactly full.
  5. Assign entry Шаблон:Mvar to the appropriate category based on the new value of Шаблон:Mvar.

Each iteration moves at least one entry to the "exactly full" category (and the last moves two), so the procedure is guaranteed to terminate after at most Шаблон:Math iterations. Each iteration can be done in Шаблон:Math time, so the table can be set up in Шаблон:Math time.

Vose[3]Шаблон:Rp points out that floating-point rounding errors may cause the guarantee referred to in step 1 to be violated. If one category empties before the other, the remaining entries may have Шаблон:Mvar set to 1 with negligible error. The solution accounting for floating point is sometimes called the Walker-Vose method or the Vose alias method.

The Alias structure is not unique.

As the lookup procedure is slightly faster if Шаблон:Math (because Шаблон:Mvar does not need to be consulted), one goal during table generation is to maximize the sum of the Шаблон:Mvar. Doing this optimally turns out to be NP hard,[5]Шаблон:Rp but a greedy algorithm comes reasonably close: rob from the richest and give to the poorest. That is, at each step choose the largest Шаблон:Mvar and the smallest Шаблон:Mvar. Because this requires sorting the Шаблон:Mvar, it requires Шаблон:Math time.

Efficiency

Although the alias method is very efficient if generating a uniform deviate is itself fast, there are cases where it is far from optimal in terms of random bit usage. This is because it uses a full-precision random variate Шаблон:Mvar each time, even when only a few random bits are needed.

One case arises when the probabilities are particularly well balanced, so many Шаблон:Math and Шаблон:Mvar is not needed. Generating Шаблон:Mvar is a waste of time. For example if Шаблон:Math, then a 32-bit random variate Шаблон:Mvar could be used to make 32 choices, but the alias method will only generate one.

Another case arises when the probabilities are strongly unbalanced, so many Шаблон:Math. For example if Шаблон:Math and Шаблон:Math, then the great majority of the time, only a few random bits are required to determine that case 1 applies. In such cases, the table method described by Marsaglia et al.[5]Шаблон:Rp is more efficient. If we make many choices with the same probability we can on average require much less than one unbiased random bit. Using arithmetic coding techniques arithmetic we can approach the limit given by the binary entropy function.

Literature

Implementations

References

Шаблон:Reflist

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite journal
  2. ↑ Шаблон:Cite journal
  3. ↑ 3,0 3,1 Шаблон:Cite journal
  4. ↑ Шаблон:Cite web
  5. ↑ 5,0 5,1 5,2 Шаблон:Citation
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Alias_method&oldid=13063126