{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:15:50Z","timestamp":1742937350955,"version":"3.40.3"},"publisher-location":"Heidelberg","reference-count":48,"publisher":"Physica-Verlag HD","isbn-type":[{"type":"print","value":"9783790826036"},{"type":"electronic","value":"9783790826043"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-7908-2604-3_1","type":"book-chapter","created":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T10:41:11Z","timestamp":1289212871000},"page":"3-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity Questions in Non-Uniform Random Variate Generation"],"prefix":"10.1007","author":[{"given":"Luc","family":"Devroye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,9,30]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF02293108","volume":"12","author":"J.H. Ahrens","year":"1974","unstructured":"AHRENS, J.H. and DIETER, U. (1974): Computer methods for sampling from gamma, beta, Poisson and binomial distributions. Computing, vol. 12, pp. 223\u2013246.","journal-title":"Computing"},{"key":"1_CR2","volume-title":"The Classical Moment Problem","author":"N.I. Akhiezer","year":"1965","unstructured":"AKHIEZER, N.I. (1965): The Classical Moment Problem, Hafner, New York."},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1214\/EJP.v14-596","volume":"14","author":"G. Alsmeyer","year":"2009","unstructured":"ALSMEYER, G. and IKSANOV, A. (2009): A log-type moment result for perpetuities and its application to martingales in supercritical branching random walks.\u2019 Electronic Journal of Probability, vol. 14, pp. 289\u2013313.","journal-title":"Electronic Journal of Probability"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/137926.137932","volume":"2","author":"S. Asmussen","year":"1992","unstructured":"ASMUSSEN, S., GLYNN, P. and THORISSON, H. (1992): Stationary detection in the initial transient problem. ACM Transactions on Modeling and Computer Simulation, vol. 2, pp. 130\u2013157.","journal-title":"ACM Transactions on Modeling and Computer Simulation"},{"key":"1_CR5","first-page":"779","volume":"62","author":"R.W. Bailey","year":"1994","unstructured":"BAILEY, R.W. (1994): Polar generation of random variates with the t distribution (1994): Mathematics of Computation, vol. 62, pp. 779\u2013781.","journal-title":"Mathematics of Computation"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"855","DOI":"10.2307\/1427027","volume":"14","author":"L. Bondesson","year":"1982","unstructured":"BONDESSON, L. (1982): On simulation from infinitely divisible distributions. Advances in Applied Probability, vol. 14, pp. 855\u2013869.","journal-title":"Advances in Applied Probability"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1214\/aoms\/1177706645","volume":"29","author":"G.E.P. Box","year":"1958","unstructured":"BOX, G.E.P. and M\u00dcLLER, M.E. (1958): A note on the generation of random normal deviates. Annals of Mathematical Statistics, vol. 29, pp. 610\u2013611.","journal-title":"Annals of Mathematical Statistics"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"340","DOI":"10.2307\/2285309","volume":"71","author":"J.M. Chambers","year":"1976","unstructured":"CHAMBERS J.M., MALLOWS, C.L. and STUCK, B.W. (1976): A method for simulating stable random variables. Journal of the American Statistical Association, vol. 71, pp. 340\u2013344.","journal-title":"Journal of the American Statistical Association"},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1080\/01966324.1981.10737080","volume":"1","author":"L. Devroye","year":"1981","unstructured":"DEVROYE, L. (1981a): The series method in random variate generation and its application to the Kolmogorov-Smirnov distribution. American Journal of Mathematical and Management Sciences, vol. 1, pp. 359\u2013379.","journal-title":"American Journal of Mathematical and Management Sciences"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/0898-1221(81)90038-9","volume":"7","author":"L. Devroye","year":"1981","unstructured":"DEVROYE, L. (1981b): The computer generation of random variables with a given characteristic function. Computers and Mathematics with Applications, vol. 7, pp. 547\u2013552.","journal-title":"Computers and Mathematics with Applications"},{"key":"1_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Non-Uniform Random Variate Generation","author":"L. Devroye","year":"1986","unstructured":"DEVROYE, L. (1986a): Non-Uniform Random Variate Generation, Springer-Verlag, New York."},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1137\/0146046","volume":"46","author":"L. Devroye","year":"1986","unstructured":"DEVROYE, L. (1986b): An automatic method for generating random variables with a given characteristic function. SIAM Journal of Applied Mathematics, vol. 46, pp. 698\u2013719.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0378-4754(89)90054-2","volume":"31","author":"L. Devroye","year":"1989","unstructured":"DEVROYE, L. (1989): On random variate generation when only moments or Fourier coefficients are known. Mathematics and Computers in Simulation, vol. 31, pp. 71\u201389.","journal-title":"Mathematics and Computers in Simulation"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1137\/0912006","volume":"12","author":"L. Devroye","year":"1991","unstructured":"DEVROYE, L. (1991): Algorithms for generating discrete random variables with a given generating function or a given moment sequence. SIAM Journal on Scientific and Statistical Computing, vol. 12, pp. 107\u2013126.","journal-title":"SIAM Journal on Scientific and Statistical Computing"},{"key":"1_CR15","first-page":"265","volume-title":"1996 Winter Simulation Conference Proceedings","author":"L. Devroye","year":"1996","unstructured":"DEVROYE, L. (1996): Random variate generation in one line of code. In: 1996 Winter Simulation Conference Proceedings, Charnes, J.M., Morrice, D.J., Brunner D.T. and Swain J.J. (eds.), pp. 265\u2013272, ACM, San Diego, CA."},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"2785","DOI":"10.1016\/S0167-7152(96)00039-9","volume":"31","author":"L. Devroye","year":"1997","unstructured":"DEVROYE, L. (1997): Simulating theta random variates. Statistics and Probability Letters, vol. 31, pp. 2785\u20132791.","journal-title":"Statistics and Probability Letters"},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1214\/ECP.v5-1024","volume":"5","author":"L. Devroye","year":"2000","unstructured":"DEVROYE, L., FILL, J., and NEININGER, R. (2000): Perfect simulation from the quicksort limit distribution. Electronic Communications in Probability, vol. 5, pp. 95\u201399.","journal-title":"Electronic Communications in Probability"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1023\/A:1011470225335","volume":"3","author":"L. Devroye","year":"2001","unstructured":"DEVROYE, L. (2001): Simulating perpetuities. Methodologies and Computing in Applied Probability, vol. 3, pp. 97\u2013115.","journal-title":"Methodologies and Computing in Applied Probability"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1239\/aap\/1025131226","volume":"34","author":"L. Devroye","year":"2002","unstructured":"DEVROYE, L. and NEININGER, R. (2002): Density approximation and exact simulation of random variables that are solutions of fixed-point equations. Advances of Applied Probability, vol. 34, pp. 441\u2013468.","journal-title":"Advances of Applied Probability"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"2251","DOI":"10.1016\/j.spl.2009.07.028","volume":"21","author":"L. Devroye","year":"2009","unstructured":"DEVROYE, L. (2009): On exact simulation algorithms for some distributions related to Jacobi theta functions. Statistics and Probability Letters, vol. 21, pp. 2251\u20132259.","journal-title":"Statistics and Probability Letters"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.spl.2009.10.013","volume":"80","author":"L. Devroye","year":"2010","unstructured":"DEVROYE, L. and FAWZI, O. (2010): Simulating the Dickman distribution. Statistics and Probability Letters, vol. 80, pp. 242\u2013247.","journal-title":"Statistics and Probability Letters"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1214\/aoap\/1027961037","volume":"8","author":"J. Fill","year":"1998","unstructured":"FILL, J. (1998): An interruptible algorithm for perfect sampling via Markov chains. The Annals of Applied Probability, vol. 8, pp. 131\u2013162.","journal-title":"The Annals of Applied Probability"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"FILL, J.A. and HUBER, M (2009): Perfect simulation of perpetuities, To appear.","DOI":"10.1214\/EJP.v15-734"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/0196-6774(86)90014-3","volume":"7","author":"P. Flajolet","year":"1986","unstructured":"FLAJOLET, P. and SAHEB, N. (1986): The complexity of generating an exponentially distributed variate. Journal of Algorithms, vol. 7, pp. 463\u2013488.","journal-title":"Journal of Algorithms"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"1195","DOI":"10.1214\/aop\/1019160331","volume":"28","author":"C.M. Goldie","year":"2000","unstructured":"GOLDIE, C.M. and MALLER, R.A. (2000): Stability of perpetuities. Annals of Probability, vol. 28, pp. 1195\u20131218.","journal-title":"Annals of Probability"},{"key":"1_CR26","first-page":"301","volume-title":"Monte Carlo Methods","author":"P.J. Green","year":"2000","unstructured":"GREEN, P.J. and MURDOCH, D.J. (2000): Exact sampling for Bayesian inference: towards general purpose algorithms (with discussion). In: Monte Carlo Methods, Bernardo, J.M., Berger, J.O., Dawid, A.P. and Smith, A.F.M. (eds.), pp. 301\u2013321, Bayesian Statistics, vol. 6, Oxford university Press, Oxford."},{"key":"1_CR27","doi-asserted-by":"crossref","DOI":"10.1515\/9781400875597","volume-title":"Approximations for Digital Computers","author":"C. Hastings","year":"1955","unstructured":"HASTINGS, C. (1955): Approximations for Digital Computers, Princeton University Press, Princeton, New Jersey."},{"key":"1_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05946-3","volume-title":"Automatic Nonuniform Random Variate Generation","author":"W. H\u00d6Rmann","year":"2004","unstructured":"H\u00d6RMANN, W., LEYDOLD, J., and DERFLINGER, G. (2004): Automatic Nonuniform Random Variate Generation, Springer-Verlag, Berlin."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"D. Huffman","year":"1952","unstructured":"HUFFMAN, D. (1952): A method for the construction of minimum-redundancy codes. Proceedings of the IRE, vol. 40, pp. 1098\u20131101.","journal-title":"Proceedings of the IRE"},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1214\/aop\/1176996309","volume":"3","author":"M. Kanter","year":"1975","unstructured":"KANTER, M. (1975): Stable densities under change of scale and total variation inequalities. Annals of Probability, vol. 3, pp. 697\u2013707.","journal-title":"Annals of Probability"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1145\/175007.175019","volume":"4","author":"M.S. Keane","year":"1994","unstructured":"KEANE, M.S., and O\u2019BRIEN, G.L. (1994): A Bernoulli factory. ACM Transactions on Modeling and Computer Simulation, vol. 4, pp. 213\u2013219.","journal-title":"ACM Transactions on Modeling and Computer Simulation"},{"key":"1_CR32","unstructured":"KENDALL, W. (2004): Random walk CFTP. Th\u00f6nnes ed., Department of Statistics, University of Warwick."},{"key":"1_CR33","first-page":"357","volume-title":"Algorithms and Complexity","author":"D.E. Knuth","year":"1976","unstructured":"KNUTH, D.E. and YAO, A.C. (1976): The complexity of nonuniform random number generation. in: Algorithms and Complexity, Traub, J.E. (ed.), pp. 357\u2013428, Academic Press, New York, N.Y.."},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1073\/pnas.61.1.25","volume":"60","author":"G. Marsaglia","year":"1968","unstructured":"MARSAGLIA, G. (1968): Random numbers fall mainly in the planes. Proceedings of the National Academy of Sciences, vol. 60, pp. 25\u201328.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1214\/aoap\/1177005878","volume":"1","author":"G. Marsaglia","year":"1991","unstructured":"MARSAGLIA, G. and ZAMAN, A. (1991): A new class of random number generators. Annals of Applied Probability, vol. 1, pp. 462\u2013480.","journal-title":"Annals of Applied Probability"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"METROPOLIS, N., ROSENBLUTH, A., ROSENBLUTH, M., TELLER, A., and TELLER, E. (1953): Equations of state calculations by fast computing machines. Journal of Chemical Physics, vol. 21, p. 1087\u20131091.","journal-title":"Journal of Chemical Physics"},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1111\/1467-9469.00116","volume":"25","author":"D.J. Murdoch","year":"1998","unstructured":"MURDOCH, D.J. and GREEN, P.J. (1998): Exact sampling from a continous space. Scandinavian Journal of Statistics, vol. 25, pp. 483\u2013502.","journal-title":"Scandinavian Journal of Statistics"},{"key":"1_CR38","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.0.CO;2-O","volume":"9","author":"G.J. Propp","year":"1996","unstructured":"PROPP, G.J. and WILSON, D.B. (1996): Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms, vol. 9, pp. 223\u2013252.","journal-title":"Random Structures and Algorithms"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02679611","volume":"29","author":"U. R\u00f6sler","year":"2001","unstructured":"R\u00d6SLER, U. and R\u00dcSHENDORF, L. (2001): The contraction method for recursive algorithms. Algorithmica, vol. 29, pp. 3\u201333.","journal-title":"Algorithmica"},{"key":"1_CR40","volume-title":"L\u00e9vy Processes and Infinitely Divisible Distributions","author":"K. Sato","year":"2000","unstructured":"K. SATO (2000): L\u00e9vy Processes and Infinitely Divisible Distributions, Cambridge University Press, Cambridge."},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"158","DOI":"10.2307\/2347441","volume":"33","author":"U. Ulrich","year":"1984","unstructured":"ULRICH, U. (1984): Computer generation of distributions on the m-sphere. Applied Statistics, vol. 33, pp. 158\u2013163.","journal-title":"Applied Statistics"},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"750","DOI":"10.2307\/1426858","volume":"11","author":"W. Vervaat","year":"1979","unstructured":"VERVAAT, W. (1979): On a stochastic difference equation and a representation of non-negative infinitely divisible random variables. Advances in Applied Probability, vol. 11, pp. 750\u2013783.","journal-title":"Advances in Applied Probability"},{"key":"1_CR43","first-page":"768","volume":"5","author":"J. Von Neumann","year":"1963","unstructured":"VON NEUMANN, J. (1963): Various techniques used in connection with random digits. Collected Works, vol. 5, pp. 768\u2013770, Pergamon Press. Also in (1951): Monte Carlo Method. National Bureau of Standards Series, Vol. 12, pp. 36-38.","journal-title":"Collected Works"},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"WILSON, D.B. (2000): Layered multishift coupling for use in perfect sampling algorithms (with a primer on CFTP). In: Monte Carlo Methods, Madras, N. (ed.), pp. 141\u2013176, Fields Institute Communications, vol. 6, American Mathematical Society.","DOI":"10.1090\/fic\/026\/11"},{"key":"1_CR45","first-page":"207","volume":"1","author":"V. M. Zolotarev","year":"1959","unstructured":"ZOLOTAREV, V. M. (1959): On analytic properties of stable distribution laws. Selected Translations in Mathematical Statistics and Probability, vol. 1, pp. 207\u2013211.","journal-title":"Selected Translations in Mathematical Statistics and Probability"},{"key":"1_CR46","first-page":"84","volume":"6","author":"V. M. Zolotarev","year":"1966","unstructured":"ZOLOTAREV, V. M. (1966): On the representation of stable laws by integrals. Selected Translations in Mathematical Statistics and Probability, vol. 6, pp. 84\u201388.","journal-title":"Selected Translations in Mathematical Statistics and Probability"},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"ZOLOTAREV, V. M. (1981): Integral transformations of distributions and estimates of parameters of multidimensional spherically symmetric stable laws. In: Contributions to Probability, pp. 283\u2013305, Academic Press.","DOI":"10.1016\/B978-0-12-274460-0.50029-1"},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"ZOLOTAREV, V. M. (1986): One-Dimensional Stable Distributions, American Mathematical Society, Providence, R.I..","DOI":"10.1090\/mmono\/065"}],"container-title":["Proceedings of COMPSTAT'2010"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-7908-2604-3_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T00:30:37Z","timestamp":1674088237000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-7908-2604-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783790826036","9783790826043"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-7908-2604-3_1","relation":{},"subject":[],"published":{"date-parts":[[2010]]},"assertion":[{"value":"30 September 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}