The complexity of generating an exponentially distributed variate |
| |
Authors: | Philippe Flajolet Nasser Saheb |
| |
Abstract: | We analyze in detail an almost optimal algorithm for generating an exponentially distributed variate. The algorithm is due to Knuth and Yao and relies on a method which goes back to J. von Neumann. It is shown here that it can generate k bits of an exponentially distributed variate using an average of about k + 5.67974692 coin flippings. This solves a problem left open by Knuth and Yao. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |