Inverse transform sampling

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Inverse transform sampling - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"19a36b75-dbc0-4a8e-891e-5c656cd69dbf","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Inverse_transform_sampling","wgTitle":"Inverse transform sampling","wgCurRevisionId":1244749103,"wgRevisionId":1244749103,"wgArticleId":45705,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Monte Carlo methods","Non-uniform random numbers"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Inverse_transform_sampling","wgRelevantArticleId":45705,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive": false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1377019","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming", "ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/6/68/Inverse_transform_sampling.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1187"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/6/68/Inverse_transform_sampling.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="792"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="633"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Inverse transform sampling - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Inverse_transform_sampling"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Inverse_transform_sampling&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Inverse_transform_sampling"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Inverse_transform_sampling rootpage-Inverse_transform_sampling skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Inverse+transform+sampling" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Inverse+transform+sampling" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Inverse+transform+sampling" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Inverse+transform+sampling" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Formal_statement" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formal_statement"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Formal statement</span> </div> </a> <ul id="toc-Formal_statement-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Intuition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Intuition"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Intuition</span> </div> </a> <ul id="toc-Intuition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_method" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#The_method"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>The method</span> </div> </a> <ul id="toc-The_method-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Proof_of_correctness" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Proof_of_correctness"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Proof of correctness</span> </div> </a> <ul id="toc-Proof_of_correctness-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Truncated_distribution" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Truncated_distribution"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Truncated distribution</span> </div> </a> <ul id="toc-Truncated_distribution-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Reduction_of_the_number_of_inversions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Reduction_of_the_number_of_inversions"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Reduction of the number of inversions</span> </div> </a> <ul id="toc-Reduction_of_the_number_of_inversions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Software_implementations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Software_implementations"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Software implementations</span> </div> </a> <ul id="toc-Software_implementations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Inverse transform sampling</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 12 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-12" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">12 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Mostreig_de_transformaci%C3%B3_inversa" title="Mostreig de transformació inversa – Catalan" lang="ca" hreflang="ca" data-title="Mostreig de transformació inversa" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Inversionsmethode" title="Inversionsmethode – German" lang="de" hreflang="de" data-title="Inversionsmethode" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/M%C3%A9todo_de_la_transformada_inversa" title="Método de la transformada inversa – Spanish" lang="es" hreflang="es" data-title="Método de la transformada inversa" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%B1%D9%88%D8%B4_%D8%AA%D8%A8%D8%AF%DB%8C%D9%84_%D9%85%D8%B9%DA%A9%D9%88%D8%B3" title="روش تبدیل معکوس – Persian" lang="fa" hreflang="fa" data-title="روش تبدیل معکوس" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/M%C3%A9thode_de_la_transform%C3%A9e_inverse" title="Méthode de la transformée inverse – French" lang="fr" hreflang="fr" data-title="Méthode de la transformée inverse" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Metodo_dell%27inversione" title="Metodo dell'inversione – Italian" lang="it" hreflang="it" data-title="Metodo dell'inversione" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%93%D7%92%D7%99%D7%9E%D7%94_%D7%9E%D7%94%D7%A2%D7%AA%D7%A7%D7%94_%D7%94%D7%95%D7%A4%D7%9B%D7%99%D7%AA" title="דגימה מהעתקה הופכית – Hebrew" lang="he" hreflang="he" data-title="דגימה מהעתקה הופכית" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E9%80%86%E9%96%A2%E6%95%B0%E6%B3%95" title="逆関数法 – Japanese" lang="ja" hreflang="ja" data-title="逆関数法" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/M%C3%A9todo_da_transforma%C3%A7%C3%A3o_inversa" title="Método da transformação inversa – Portuguese" lang="pt" hreflang="pt" data-title="Método da transformação inversa" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F" title="Метод обратного преобразования – Russian" lang="ru" hreflang="ru" data-title="Метод обратного преобразования" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-su mw-list-item"><a href="https://su.wikipedia.org/wiki/Inverse_transform_sampling_method" title="Inverse transform sampling method – Sundanese" lang="su" hreflang="su" data-title="Inverse transform sampling method" data-language-autonym="Sunda" data-language-local-name="Sundanese" class="interlanguage-link-target"><span>Sunda</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E9%80%86%E5%8F%98%E6%8D%A2%E9%87%87%E6%A0%B7" title="逆变换采样 – Chinese" lang="zh" hreflang="zh" data-title="逆变换采样" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1377019#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Inverse_transform_sampling" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Inverse_transform_sampling" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Inverse_transform_sampling"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Inverse_transform_sampling"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Inverse_transform_sampling" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Inverse_transform_sampling" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&oldid=1244749103" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Inverse_transform_sampling&id=1244749103&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FInverse_transform_sampling"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FInverse_transform_sampling"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Inverse_transform_sampling&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Inverse_transform_sampling&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1377019" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Basic method for pseudo-random number sampling</div> <p><b>Inverse transform sampling</b> (also known as <b>inversion sampling</b>, the <b>inverse probability integral transform</b>, the <b>inverse transformation method</b>, or the <b><a href="/wiki/Nikolai_Smirnov_(mathematician)" title="Nikolai Smirnov (mathematician)">Smirnov</a> transform</b>) is a basic method for <a href="/wiki/Pseudo-random_number_sampling" class="mw-redirect" title="Pseudo-random number sampling">pseudo-random number sampling</a>, i.e., for generating sample numbers at <a href="/wiki/Random" class="mw-redirect" title="Random">random</a> from any <a href="/wiki/Probability_distribution" title="Probability distribution">probability distribution</a> given its <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a>. </p><p>Inverse transformation sampling takes <a href="/wiki/Continuous_uniform_distribution" title="Continuous uniform distribution">uniform samples</a> of a number <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span> between 0 and 1, interpreted as a probability, and then returns the smallest number <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {R} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {R} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c6d458566aec47a7259762034790c8981aefab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.848ex; height:2.176ex;" alt="{\displaystyle x\in \mathbb {R} }"></span> such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)\geq u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(x)\geq u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d14e82c5dc584ff222d2472098bd3741f7150af0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.308ex; height:2.843ex;" alt="{\displaystyle F(x)\geq u}"></span> for the <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> of a random variable. For example, imagine that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> is the standard <a href="/wiki/Normal_distribution" title="Normal distribution">normal distribution</a> with mean zero and standard deviation one. The table below shows samples taken from the uniform distribution and their representation on the standard normal distribution. </p> <table class="wikitable floatright"> <caption>Transformation from uniform sample to normal </caption> <tbody><tr> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F^{-1}(u)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F^{-1}(u)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff135622f7bf096dc6291de89f092355d9eb712a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.287ex; height:3.176ex;" alt="{\displaystyle F^{-1}(u)}"></span> </th></tr> <tr> <td>.5</td> <td>0 </td></tr> <tr> <td>.975</td> <td>1.95996 </td></tr> <tr> <td>.995</td> <td>2.5758 </td></tr> <tr> <td>.999999</td> <td>4.75342 </td></tr> <tr> <td>1-2<sup>−52</sup></td> <td>8.12589 </td></tr></tbody></table> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Inverse_transform_sampling.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/68/Inverse_transform_sampling.png/360px-Inverse_transform_sampling.png" decoding="async" width="360" height="356" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/6/68/Inverse_transform_sampling.png 1.5x" data-file-width="382" data-file-height="378" /></a><figcaption>Inverse transform sampling for normal distribution</figcaption></figure> <p>We are randomly choosing a proportion of the area under the curve and returning the number in the domain such that exactly this proportion of the area occurs to the left of that number. Intuitively, we are unlikely to choose a number in the far end of tails because there is very little area in them which would require choosing a number very close to zero or one. </p><p>Computationally, this method involves computing the <a href="/wiki/Quantile_function" title="Quantile function">quantile function</a> of the distribution — in other words, computing the <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> (CDF) of the distribution (which maps a number in the domain to a probability between 0 and 1) and then inverting that function. This is the source of the term "inverse" or "inversion" in most of the names for this method. Note that for a <a href="/wiki/Discrete_distribution" class="mw-redirect" title="Discrete distribution">discrete distribution</a>, computing the CDF is not in general too difficult: we simply add up the individual probabilities for the various points of the distribution. For a <a href="/wiki/Continuous_distribution" class="mw-redirect" title="Continuous distribution">continuous distribution</a>, however, we need to integrate the <a href="/wiki/Probability_density_function" title="Probability density function">probability density function</a> (PDF) of the distribution, which is impossible to do analytically for most distributions (including the <a href="/wiki/Normal_distribution" title="Normal distribution">normal distribution</a>). As a result, this method may be computationally inefficient for many distributions and other methods are preferred; however, it is a useful method for building more generally applicable samplers such as those based on <a href="/wiki/Rejection_sampling" title="Rejection sampling">rejection sampling</a>. </p><p>For the <a href="/wiki/Normal_distribution" title="Normal distribution">normal distribution</a>, the lack of an analytical expression for the corresponding quantile function means that other methods (e.g. the <a href="/wiki/Box%E2%80%93Muller_transform" title="Box–Muller transform">Box–Muller transform</a>) may be preferred computationally. It is often the case that, even for simple distributions, the inverse transform sampling method can be improved on:<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> see, for example, the <a href="/wiki/Ziggurat_algorithm" title="Ziggurat algorithm">ziggurat algorithm</a> and <a href="/wiki/Rejection_sampling" title="Rejection sampling">rejection sampling</a>. On the other hand, it is possible to approximate the quantile function of the normal distribution extremely accurately using moderate-degree polynomials, and in fact the method of doing this is fast enough that inversion sampling is now the default method for sampling from a normal distribution in the statistical package <a href="/wiki/R_(programming_language)" title="R (programming language)">R</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Formal_statement">Formal statement</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=1" title="Edit section: Formal statement"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For any <a href="/wiki/Random_variable" title="Random variable">random variable</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\in \mathbb {R} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\in \mathbb {R} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8fb5134661be014f6cc703c2330ed3dc9088a2bb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.499ex; height:2.176ex;" alt="{\displaystyle X\in \mathbb {R} }"></span>, the random variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}^{-1}(U)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}^{-1}(U)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c638830d72f9265f58ab6c9172fb4e680fd953bd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.739ex; height:3.343ex;" alt="{\displaystyle F_{X}^{-1}(U)}"></span> has the same distribution as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c300943c1b75a25a7923e8bfb36e18e0074b3f30" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.148ex; height:3.343ex;" alt="{\displaystyle F_{X}^{-1}}"></span> is the <a href="/wiki/Cumulative_distribution_function#Inverse_distribution_function_(quantile_function)" title="Cumulative distribution function">generalized inverse</a> of the <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}"></span> is uniform on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}"></span>.<sup id="cite_ref-mcneil2005_3-0" class="reference"><a href="#cite_note-mcneil2005-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>For <a href="/wiki/Random_variable#Continuous_random_variable" title="Random variable">continuous random variables</a>, the inverse probability integral transform is indeed the inverse of the <a href="/wiki/Probability_integral_transform" title="Probability integral transform">probability integral transform</a>, which states that for a <a href="/wiki/Continuous_random_variable" class="mw-redirect" title="Continuous random variable">continuous random variable</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> with <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span>, the random variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U=F_{X}(X)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>=</mo> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U=F_{X}(X)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/64923e985a0ae3624625f73b662594383bfcee35" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.797ex; height:2.843ex;" alt="{\displaystyle U=F_{X}(X)}"></span> is <a href="/wiki/Uniform_distribution_(continuous)" class="mw-redirect" title="Uniform distribution (continuous)">uniform</a> on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}"></span>. </p> <figure typeof="mw:File/Thumb"><a href="/wiki/File:InverseFunc.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/24/InverseFunc.png/360px-InverseFunc.png" decoding="async" width="360" height="321" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/24/InverseFunc.png/540px-InverseFunc.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/24/InverseFunc.png/720px-InverseFunc.png 2x" data-file-width="1172" data-file-height="1044" /></a><figcaption>Graph of the inversion technique from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span> to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/71a82805d469cdfa7856c11d6ee756acd1dc7174" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.88ex; height:2.843ex;" alt="{\displaystyle F(x)}"></span>. On the bottom right we see the regular function and in the top left its inversion.</figcaption></figure> <div class="mw-heading mw-heading2"><h2 id="Intuition">Intuition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=2" title="Edit section: Intuition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>From <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\sim \mathrm {Unif} [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>∼</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">U</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">f</mi> </mrow> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U\sim \mathrm {Unif} [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b6e22010588966c1d8492db40f1795db3a15aea9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.081ex; height:2.843ex;" alt="{\displaystyle U\sim \mathrm {Unif} [0,1]}"></span>, we want to generate <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> with <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">CDF</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}(x).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}(x).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d582149e1c470b2f5f587aec101a141f6068bba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.913ex; height:2.843ex;" alt="{\displaystyle F_{X}(x).}"></span> We assume <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/242727215e028fc47529c5bd7035e88cc0da25e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.266ex; height:2.843ex;" alt="{\displaystyle F_{X}(x)}"></span> to be a continuous, strictly increasing function, which provides good intuition. </p><p>We want to see if we can find some strictly monotone transformation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T:[0,1]\mapsto \mathbb {R} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>:</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo stretchy="false">↦</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T:[0,1]\mapsto \mathbb {R} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/957a365463e1db0539d89528f2f1d2e7c5e469d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.518ex; height:2.843ex;" alt="{\displaystyle T:[0,1]\mapsto \mathbb {R} }"></span>, such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(U){\overset {d}{=}}X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mover> <mo>=</mo> <mi>d</mi> </mover> </mrow> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T(U){\overset {d}{=}}X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6ebd7bbec4f91085ecdf9033a776006666d25f1b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.016ex; height:3.843ex;" alt="{\displaystyle T(U){\overset {d}{=}}X}"></span>. We will have </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}(x)=\Pr(X\leq x)=\Pr(T(U)\leq x)=\Pr(U\leq T^{-1}(x))=T^{-1}(x),{\text{ for }}x\in \mathbb {R} ,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <mi>X</mi> <mo>≤</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <mi>U</mi> <mo>≤</mo> <msup> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext> for </mtext> </mrow> <mi>x</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}(x)=\Pr(X\leq x)=\Pr(T(U)\leq x)=\Pr(U\leq T^{-1}(x))=T^{-1}(x),{\text{ for }}x\in \mathbb {R} ,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/50a402ca4cc3981d887a6aeb6340cb27d96036a3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:78.376ex; height:3.176ex;" alt="{\displaystyle F_{X}(x)=\Pr(X\leq x)=\Pr(T(U)\leq x)=\Pr(U\leq T^{-1}(x))=T^{-1}(x),{\text{ for }}x\in \mathbb {R} ,}"></span> </p><p>where the last step used that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr(U\leq y)=y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <mi>U</mi> <mo>≤</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Pr(U\leq y)=y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c4dfef25359845e5613ede3fa55250035ed410b8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.594ex; height:2.843ex;" alt="{\displaystyle \Pr(U\leq y)=y}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}"></span> is uniform on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}"></span>. </p><p>So we got <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span> to be the inverse function of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>, or, equivalently <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(u)=F_{X}^{-1}(u),u\in [0,1].}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>u</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T(u)=F_{X}^{-1}(u),u\in [0,1].}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bcd81ebf7a2ef3cbe8c03207df46fc559e6681c4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.664ex; height:3.343ex;" alt="{\displaystyle T(u)=F_{X}^{-1}(u),u\in [0,1].}"></span> </p><p>Therefore, we can generate <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}^{-1}(U).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}^{-1}(U).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4322130d1604b8bd12492f63dfafe0394ad8f51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.386ex; height:3.343ex;" alt="{\displaystyle F_{X}^{-1}(U).}"></span> </p> <div class="mw-heading mw-heading2"><h2 id="The_method">The method</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=3" title="Edit section: The method"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Generalized_inversion_method.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/87/Generalized_inversion_method.svg/360px-Generalized_inversion_method.svg.png" decoding="async" width="360" height="360" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/87/Generalized_inversion_method.svg/540px-Generalized_inversion_method.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/87/Generalized_inversion_method.svg/720px-Generalized_inversion_method.svg.png 2x" data-file-width="630" data-file-height="630" /></a><figcaption>Schematic of the inverse transform sampling. The inverse function of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=F_{X}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo>=</mo> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y=F_{X}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9f2ac1286cbf8dc2af9472f69d5fb2d9ee08de7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.52ex; height:2.843ex;" alt="{\displaystyle y=F_{X}(x)}"></span> can be defined by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">f</mi> </mrow> <mo fence="false" stretchy="false">{</mo> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>y</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d186cfabc125dce9514b3155900b438f0ee19755" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:27.837ex; height:3.343ex;" alt="{\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}}"></span>.</figcaption></figure> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Inverse_Transform_Sampling_Example.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/c/cc/Inverse_Transform_Sampling_Example.gif" decoding="async" width="360" height="360" class="mw-file-element" data-file-width="360" data-file-height="360" /></a><figcaption>An animation of how inverse transform sampling generates normally distributed random values from uniformly distributed random values</figcaption></figure> <p>The problem that the inverse transform sampling method solves is as follows: </p> <ul><li>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> be a <a href="/wiki/Random_variable" title="Random variable">random variable</a> whose distribution can be described by the <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span>.</li> <li>We want to generate values of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> which are distributed according to this distribution.</li></ul> <p>The inverse transform sampling method works as follows: </p> <ol><li><a href="/wiki/Pseudorandom_number_generator" title="Pseudorandom number generator">Generate a random number</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span> from the standard uniform distribution in the interval <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}"></span>, i.e. from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\sim \mathrm {Unif} [0,1].}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>∼</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">U</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">f</mi> </mrow> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U\sim \mathrm {Unif} [0,1].}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9e3cdfcf6e4924900b93b518404f5cc72450b08" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.728ex; height:2.843ex;" alt="{\displaystyle U\sim \mathrm {Unif} [0,1].}"></span></li> <li>Find the <a href="/wiki/Cumulative_distribution_function#Inverse_distribution_function_(quantile_function)" title="Cumulative distribution function">generalized inverse</a> of the desired CDF, i.e. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}^{-1}(u)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}^{-1}(u)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/35ab77a76e74f9cd26a4033a26ccbe50bab10864" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.287ex; height:3.343ex;" alt="{\displaystyle F_{X}^{-1}(u)}"></span>.</li> <li>Compute <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X'(u)=F_{X}^{-1}(u)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>X</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X'(u)=F_{X}^{-1}(u)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8873758b1c27fb68b603664b7af9ce98304f1be0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.206ex; height:3.343ex;" alt="{\displaystyle X'(u)=F_{X}^{-1}(u)}"></span>. The computed random variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X'(U)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>X</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X'(U)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f17c7e1d89ff0cfd9ea4ad412fcef209e9e33f2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.273ex; height:3.009ex;" alt="{\displaystyle X'(U)}"></span> has distribution <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span> and thereby the same law as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span>.</li></ol> <p>Expressed differently, given a cumulative distribution function <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span> and a uniform variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\in [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U\in [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66966a6f68e58c668e96ae0c3d72967076188f6e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.276ex; height:2.843ex;" alt="{\displaystyle U\in [0,1]}"></span>, the random variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=F_{X}^{-1}(U)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>=</mo> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X=F_{X}^{-1}(U)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d47e8c0c30eb57acfb6a06cf5a9345483e583192" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.818ex; height:3.343ex;" alt="{\displaystyle X=F_{X}^{-1}(U)}"></span> has the distribution <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/062f285db773e329f6c270cb6b65fa076996c941" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.127ex; height:2.509ex;" alt="{\displaystyle F_{X}}"></span>.<sup id="cite_ref-mcneil2005_3-1" class="reference"><a href="#cite_note-mcneil2005-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>In the continuous case, a treatment of such inverse functions as objects satisfying differential equations can be given.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Some such differential equations admit explicit <a href="/wiki/Power_series" title="Power series">power series</a> solutions, despite their non-linearity.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=4" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>As an example, suppose we have a random variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\sim \mathrm {Unif} (0,1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>∼</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">U</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">f</mi> </mrow> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U\sim \mathrm {Unif} (0,1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3c86fdfc26e7e426f8de4b9f74353f631a59ce7b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.597ex; height:2.843ex;" alt="{\displaystyle U\sim \mathrm {Unif} (0,1)}"></span> and a <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a></li></ul> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}F(x)=1-\exp(-{\sqrt {x}})\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mi>exp</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>x</mi> </msqrt> </mrow> <mo stretchy="false">)</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}F(x)=1-\exp(-{\sqrt {x}})\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9af119e388506d1d7052e6901a7e1a5b9481e1ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.168ex; height:3.176ex;" alt="{\displaystyle {\begin{aligned}F(x)=1-\exp(-{\sqrt {x}})\end{aligned}}}"></span></dd> <dd>In order to perform an inversion we want to solve for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(F^{-1}(u))=u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>=</mo> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(F^{-1}(u))=u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ad1a814969ba5c8385168464f34aa13d6001a4f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.265ex; height:3.176ex;" alt="{\displaystyle F(F^{-1}(u))=u}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}F(F^{-1}(u))&=u\\1-\exp \left(-{\sqrt {F^{-1}(u)}}\right)&=u\\F^{-1}(u)&=(-\log(1-u))^{2}\\&=(\log(1-u))^{2}\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>F</mi> <mo stretchy="false">(</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>u</mi> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> <mo>−</mo> <mi>exp</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </msqrt> </mrow> </mrow> <mo>)</mo> </mrow> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>u</mi> </mtd> </mtr> <mtr> <mtd> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>u</mi> <mo stretchy="false">)</mo> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>u</mi> <mo stretchy="false">)</mo> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}F(F^{-1}(u))&=u\\1-\exp \left(-{\sqrt {F^{-1}(u)}}\right)&=u\\F^{-1}(u)&=(-\log(1-u))^{2}\\&=(\log(1-u))^{2}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/35832b84d032486478082d0c09d578922ff91382" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.838ex; margin-top: -0.211ex; width:40.771ex; height:14.843ex;" alt="{\displaystyle {\begin{aligned}F(F^{-1}(u))&=u\\1-\exp \left(-{\sqrt {F^{-1}(u)}}\right)&=u\\F^{-1}(u)&=(-\log(1-u))^{2}\\&=(\log(1-u))^{2}\end{aligned}}}"></span></dd> <dd>From here we would perform steps one, two and three.</dd></dl> <ul><li>As another example, we use the <a href="/wiki/Exponential_distribution" title="Exponential distribution">exponential distribution</a> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{X}(x)=1-e^{-\lambda x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo>−</mo> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>λ</mi> <mi>x</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{X}(x)=1-e^{-\lambda x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d055cf11e7e6b868d96d7108787a1492e1c3b890" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.86ex; height:3.176ex;" alt="{\displaystyle F_{X}(x)=1-e^{-\lambda x}}"></span> for x ≥ 0 (and 0 otherwise). By solving y=F(x) we obtain the inverse function</li></ul> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(1-y).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>=</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>λ</mi> </mfrac> </mrow> <mi>ln</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(1-y).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/00ebbbe4af6f03fdb7e3f4e0f9462f019cf05143" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:28.579ex; height:5.343ex;" alt="{\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(1-y).}"></span></dd> <dd>It means that if we draw some <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d943dbbb0b56ca750c4d62c5b54b4ae29a773da" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.193ex; height:2.009ex;" alt="{\displaystyle y_{0}}"></span>from a <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\sim \mathrm {Unif} (0,1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>∼</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">U</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">f</mi> </mrow> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U\sim \mathrm {Unif} (0,1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3c86fdfc26e7e426f8de4b9f74353f631a59ce7b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.597ex; height:2.843ex;" alt="{\displaystyle U\sim \mathrm {Unif} (0,1)}"></span> and compute <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}=F_{X}^{-1}(y_{0})=-{\frac {1}{\lambda }}\ln(1-y_{0}),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <msubsup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> <mo stretchy="false">(</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>λ</mi> </mfrac> </mrow> <mi>ln</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{0}=F_{X}^{-1}(y_{0})=-{\frac {1}{\lambda }}\ln(1-y_{0}),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b77f75004fe5f75297aed1291b76359402e4c039" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:31.71ex; height:5.343ex;" alt="{\displaystyle x_{0}=F_{X}^{-1}(y_{0})=-{\frac {1}{\lambda }}\ln(1-y_{0}),}"></span> This <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}"></span> has exponential distribution.</dd> <dd>The idea is illustrated in the following graph:</dd></dl> <dl><dd><figure class="mw-halign-none" typeof="mw:File/Thumb"><a href="/wiki/File:Inverse_transformation_method_for_exponential_distribution.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Inverse_transformation_method_for_exponential_distribution.jpg/400px-Inverse_transformation_method_for_exponential_distribution.jpg" decoding="async" width="400" height="318" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Inverse_transformation_method_for_exponential_distribution.jpg/600px-Inverse_transformation_method_for_exponential_distribution.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Inverse_transformation_method_for_exponential_distribution.jpg/800px-Inverse_transformation_method_for_exponential_distribution.jpg 2x" data-file-width="885" data-file-height="704" /></a><figcaption>Random numbers y<sub>i</sub> are generated from a uniform distribution between 0 and 1, i.e. Y ~ U(0, 1). They are sketched as colored points on the y-axis. Each of the points is mapped according to x=F<sup>−1</sup>(y), which is shown with gray arrows for two example points. In this example, we have used an exponential distribution. Hence, for x ≥ 0, the probability density is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ϱ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>X</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>λ</mi> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>λ</mi> <mspace width="thinmathspace" /> <mi>x</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/631bb8fe4a23b552f28603499d534bdafe75e24e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.307ex; height:3.176ex;" alt="{\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}}"></span> and the cumulative distribution function is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)=1-e^{-\lambda \,x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo>−</mo> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>λ</mi> <mspace width="thinmathspace" /> <mi>x</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(x)=1-e^{-\lambda \,x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1d260de5feee719e986c011d16c20dc3e8c86e0c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.861ex; height:3.176ex;" alt="{\displaystyle F(x)=1-e^{-\lambda \,x}}"></span>. Therefore, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>=</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>ln</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> <mi>λ</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65f5845f40db7d653a905cd6ccbcb44760e8131b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:26.19ex; height:5.843ex;" alt="{\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}}"></span>. We can see that using this method, many points end up close to 0 and only few points end up having high x-values - just as it is expected for an exponential distribution.</figcaption></figure></dd> <dd>Note that the distribution does not change if we start with 1-y instead of y. For computational purposes, it therefore suffices to generate random numbers y in [0, 1] and then simply calculate</dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(y).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>=</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>λ</mi> </mfrac> </mrow> <mi>ln</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(y).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/358e08889f883f53854d66ae792a32f79f4f5741" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:24.577ex; height:5.343ex;" alt="{\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(y).}"></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Proof_of_correctness">Proof of correctness</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=5" title="Edit section: Proof of correctness"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> be a <a href="/wiki/Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a>, and let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e2a1a300038291319dc37f8cf5d1e87b6abc1ae7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.148ex; height:2.676ex;" alt="{\displaystyle F^{-1}}"></span> be its <a href="/wiki/Cumulative_distribution_function#Inverse_distribution_function_(quantile_function)" title="Cumulative distribution function">generalized inverse function</a> (using the <a href="/wiki/Infimum" class="mw-redirect" title="Infimum">infimum</a> because CDFs are weakly monotonic and <a href="/wiki/C%C3%A0dl%C3%A0g" title="Càdlàg">right-continuous</a>):<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F^{-1}(u)=\inf \;\{x\mid F(x)\geq u\}\qquad (0<u<1).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo movablelimits="true" form="prefix">inf</mo> <mspace width="thickmathspace" /> <mo fence="false" stretchy="false">{</mo> <mi>x</mi> <mo>∣</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>u</mi> <mo fence="false" stretchy="false">}</mo> <mspace width="2em" /> <mo stretchy="false">(</mo> <mn>0</mn> <mo><</mo> <mi>u</mi> <mo><</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F^{-1}(u)=\inf \;\{x\mid F(x)\geq u\}\qquad (0<u<1).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a8eaab97c61dd81fd08078048f19c053e90cc36c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.534ex; height:3.176ex;" alt="{\displaystyle F^{-1}(u)=\inf \;\{x\mid F(x)\geq u\}\qquad (0<u<1).}"></span></dd></dl> <p><i>Claim:</i> If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}"></span> is a <a href="/wiki/Uniform_distribution_(continuous)" class="mw-redirect" title="Uniform distribution (continuous)">uniform</a> random variable on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}"></span> then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F^{-1}(U)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F^{-1}(U)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/df79abcf29c321064d006d706c0b4174967187ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.739ex; height:3.176ex;" alt="{\displaystyle F^{-1}(U)}"></span> has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> as its CDF. </p><p><i>Proof:</i> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}&\Pr(F^{-1}(U)\leq x)\\&{}=\Pr(U\leq F(x))\quad &(F{\text{ is right-continuous, so }}\{u:F^{-1}(u)\leq x\}=\{u:u\leq F(x)\})\\&{}=F(x)\quad &({\text{because }}\Pr(U\leq u)=u,{\text{ when }}U{\text{ is uniform on }}[0,1])\\\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd /> <mtd> <mi></mi> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>U</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mrow class="MJX-TeXAtom-ORD"> </mrow> <mo>=</mo> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <mi>U</mi> <mo>≤</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mspace width="1em" /> </mtd> <mtd> <mo stretchy="false">(</mo> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> is right-continuous, so </mtext> </mrow> <mo fence="false" stretchy="false">{</mo> <mi>u</mi> <mo>:</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>x</mi> <mo fence="false" stretchy="false">}</mo> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>u</mi> <mo>:</mo> <mi>u</mi> <mo>≤</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mrow class="MJX-TeXAtom-ORD"> </mrow> <mo>=</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mspace width="1em" /> </mtd> <mtd> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>because </mtext> </mrow> <mo movablelimits="true" form="prefix">Pr</mo> <mo stretchy="false">(</mo> <mi>U</mi> <mo>≤</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>u</mi> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext> when </mtext> </mrow> <mi>U</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> is uniform on </mtext> </mrow> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo stretchy="false">)</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&\Pr(F^{-1}(U)\leq x)\\&{}=\Pr(U\leq F(x))\quad &(F{\text{ is right-continuous, so }}\{u:F^{-1}(u)\leq x\}=\{u:u\leq F(x)\})\\&{}=F(x)\quad &({\text{because }}\Pr(U\leq u)=u,{\text{ when }}U{\text{ is uniform on }}[0,1])\\\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98babd3462830f05cf280d73ee63039ac46e457a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:87.036ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}&\Pr(F^{-1}(U)\leq x)\\&{}=\Pr(U\leq F(x))\quad &(F{\text{ is right-continuous, so }}\{u:F^{-1}(u)\leq x\}=\{u:u\leq F(x)\})\\&{}=F(x)\quad &({\text{because }}\Pr(U\leq u)=u,{\text{ when }}U{\text{ is uniform on }}[0,1])\\\end{aligned}}}"></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Truncated_distribution">Truncated distribution</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=6" title="Edit section: Truncated distribution"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Inverse transform sampling can be simply extended to cases of <a href="/wiki/Truncated_distribution" title="Truncated distribution">truncated distributions</a> on the interval <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a,b]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a,b]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a6969e731af335df071e247ee7fb331cd1a57ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.813ex; height:2.843ex;" alt="{\displaystyle (a,b]}"></span> without the cost of rejection sampling: the same algorithm can be followed, but instead of generating a random number <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span> uniformly distributed between 0 and 1, generate <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span> uniformly distributed between <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(a)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fc7c034f57f1a8ef417737a9170547d644b6153b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.78ex; height:2.843ex;" alt="{\displaystyle F(a)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47408a5d641e07bbc89f62d441c6e936d959c167" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.548ex; height:2.843ex;" alt="{\displaystyle F(b)}"></span>, and then again take <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F^{-1}(u)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F^{-1}(u)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff135622f7bf096dc6291de89f092355d9eb712a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.287ex; height:3.176ex;" alt="{\displaystyle F^{-1}(u)}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Reduction_of_the_number_of_inversions">Reduction of the number of inversions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=7" title="Edit section: Reduction of the number of inversions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In order to obtain a large number of samples, one needs to perform the same number of inversions of the distribution. One possible way to reduce the number of inversions while obtaining a large number of samples is the application of the so-called Stochastic Collocation Monte Carlo sampler (SCMC sampler) within a <a href="/wiki/Polynomial_chaos" title="Polynomial chaos">polynomial chaos</a> expansion framework. This allows us to generate any number of Monte Carlo samples with only a few inversions of the original distribution with independent samples of a variable for which the inversions are analytically available, for example the standard normal variable.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Software_implementations">Software implementations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=8" title="Edit section: Software implementations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are software implementations available for applying the inverse sampling method by using numerical approximations of the inverse in the case that it is not available in closed form. For example, an approximation of the inverse can be computed if the user provides some information about the distributions such as the PDF <sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> or the CDF. </p> <ul><li>C library UNU.RAN <sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup></li> <li>R library Runuran <sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li> <li>Python subpackage sampling in <a href="/wiki/SciPy" title="SciPy">scipy.stats</a><sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup></li></ul> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=9" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Probability_integral_transform" title="Probability integral transform">Probability integral transform</a></li> <li><a href="/wiki/Copula_(statistics)" title="Copula (statistics)">Copula</a>, defined by means of probability integral transform.</li> <li><a href="/wiki/Quantile_function" title="Quantile function">Quantile function</a>, for the explicit construction of inverse CDFs.</li> <li><a href="/wiki/Cumulative_distribution_function#Inverse_distribution_function_(quantile_function)" title="Cumulative distribution function">Inverse distribution function</a> for a precise mathematical definition for distributions with discrete components.</li> <li><a href="/wiki/Rejection_sampling" title="Rejection sampling">Rejection sampling</a> is another common technique to generate random variates that does not rely on inversion of the CDF.</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Inverse_transform_sampling&action=edit&section=10" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFLuc_Devroye1986" class="citation book cs1">Luc Devroye (1986). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140818200854/http://www.eirene.de/Devroye.pdf"><i>Non-Uniform Random Variate Generation</i></a> <span class="cs1-format">(PDF)</span>. New York: Springer-Verlag. Archived from <a rel="nofollow" class="external text" href="http://www.eirene.de/Devroye.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2014-08-18<span class="reference-accessdate">. Retrieved <span class="nowrap">2012-04-12</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Non-Uniform+Random+Variate+Generation&rft.place=New+York&rft.pub=Springer-Verlag&rft.date=1986&rft.au=Luc+Devroye&rft_id=http%3A%2F%2Fwww.eirene.de%2FDevroye.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://stat.ethz.ch/R-manual/R-devel/library/base/html/Random.html">"R: Random Number Generation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=R%3A+Random+Number+Generation&rft_id=https%3A%2F%2Fstat.ethz.ch%2FR-manual%2FR-devel%2Flibrary%2Fbase%2Fhtml%2FRandom.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-mcneil2005-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-mcneil2005_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-mcneil2005_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMcNeilFreyEmbrechts2005" class="citation book cs1">McNeil, Alexander J.; Frey, Rüdiger; Embrechts, Paul (2005). <i>Quantitative risk management</i>. Princeton Series in Finance. Princeton University Press, Princeton, NJ. p. 186. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-691-12255-5" title="Special:BookSources/0-691-12255-5"><bdi>0-691-12255-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Quantitative+risk+management&rft.series=Princeton+Series+in+Finance&rft.pages=186&rft.pub=Princeton+University+Press%2C+Princeton%2C+NJ&rft.date=2005&rft.isbn=0-691-12255-5&rft.aulast=McNeil&rft.aufirst=Alexander+J.&rft.au=Frey%2C+R%C3%BCdiger&rft.au=Embrechts%2C+Paul&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSteinbrecherShaw2008" class="citation journal cs1">Steinbrecher, György; Shaw, William T. (19 March 2008). "Quantile mechanics". <i>European Journal of Applied Mathematics</i>. <b>19</b> (2). <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0956792508007341">10.1017/S0956792508007341</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6899308">6899308</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=European+Journal+of+Applied+Mathematics&rft.atitle=Quantile+mechanics&rft.volume=19&rft.issue=2&rft.date=2008-03-19&rft_id=info%3Adoi%2F10.1017%2FS0956792508007341&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A6899308%23id-name%3DS2CID&rft.aulast=Steinbrecher&rft.aufirst=Gy%C3%B6rgy&rft.au=Shaw%2C+William+T.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFArridgeMaassÖktemSchönlieb2019" class="citation journal cs1">Arridge, Simon; Maass, Peter; Öktem, Ozan; Schönlieb, Carola-Bibiane (2019). <a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0962492919000059">"Solving inverse problems using data-driven models"</a>. <i>Acta Numerica</i>. <b>28</b>: 1–174. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0962492919000059">10.1017/S0962492919000059</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0962-4929">0962-4929</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:197480023">197480023</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Numerica&rft.atitle=Solving+inverse+problems+using+data-driven+models&rft.volume=28&rft.pages=1-174&rft.date=2019&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A197480023%23id-name%3DS2CID&rft.issn=0962-4929&rft_id=info%3Adoi%2F10.1017%2FS0962492919000059&rft.aulast=Arridge&rft.aufirst=Simon&rft.au=Maass%2C+Peter&rft.au=%C3%96ktem%2C+Ozan&rft.au=Sch%C3%B6nlieb%2C+Carola-Bibiane&rft_id=https%3A%2F%2Fdoi.org%2F10.1017%252FS0962492919000059&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLuc_Devroye1986" class="citation book cs1">Luc Devroye (1986). <a rel="nofollow" class="external text" href="http://luc.devroye.org/chapter_two.pdf">"Section 2.2. Inversion by numerical solution of <i>F</i>(<i>X</i>) = <i>U</i>"</a> <span class="cs1-format">(PDF)</span>. <i>Non-Uniform Random Variate Generation</i>. New York: Springer-Verlag.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Section+2.2.+Inversion+by+numerical+solution+of+F%28X%29+%3D+U&rft.btitle=Non-Uniform+Random+Variate+Generation&rft.place=New+York&rft.pub=Springer-Verlag&rft.date=1986&rft.au=Luc+Devroye&rft_id=http%3A%2F%2Fluc.devroye.org%2Fchapter_two.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">L.A. Grzelak, J.A.S. Witteveen, M. Suarez, and C.W. Oosterlee. The stochastic collocation Monte Carlo sampler: Highly efficient sampling from “expensive” distributions. <a rel="nofollow" class="external free" href="https://ssrn.com/abstract=2529691">https://ssrn.com/abstract=2529691</a></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDerflingerHörmannLeydold2010" class="citation journal cs1">Derflinger, Gerhard; Hörmann, Wolfgang; Leydold, Josef (2010). <a rel="nofollow" class="external text" href="https://epub.wu.ac.at/664/1/document.pdf">"Random variate generation by numerical inversion when only the density is known"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Transactions on Modeling and Computer Simulation</i>. <b>20</b> (4). <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F945511.945517">10.1145/945511.945517</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Modeling+and+Computer+Simulation&rft.atitle=Random+variate+generation+by+numerical+inversion+when+only+the+density+is+known&rft.volume=20&rft.issue=4&rft.date=2010&rft_id=info%3Adoi%2F10.1145%2F945511.945517&rft.aulast=Derflinger&rft.aufirst=Gerhard&rft.au=H%C3%B6rmann%2C+Wolfgang&rft.au=Leydold%2C+Josef&rft_id=https%3A%2F%2Fepub.wu.ac.at%2F664%2F1%2Fdocument.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://statmath.wu.ac.at/unuran/index.html">"UNU.RAN - Universal Non-Uniform RANdom number generators"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=UNU.RAN+-+Universal+Non-Uniform+RANdom+number+generators&rft_id=https%3A%2F%2Fstatmath.wu.ac.at%2Funuran%2Findex.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://cran.r-project.org/package=Runuran">"Runuran: R Interface to the 'UNU.RAN' Random Variate Generators"</a>. 17 January 2023.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Runuran%3A+R+Interface+to+the+%27UNU.RAN%27+Random+Variate+Generators&rft.date=2023-01-17&rft_id=https%3A%2F%2Fcran.r-project.org%2Fpackage%3DRunuran&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.scipy.org/doc/scipy/reference/stats.sampling.html">"Random Number Generators (Scipy.stats.sampling) — SciPy v1.12.0 Manual"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Random+Number+Generators+%28Scipy.stats.sampling%29+%E2%80%94+SciPy+v1.12.0+Manual&rft_id=https%3A%2F%2Fdocs.scipy.org%2Fdoc%2Fscipy%2Freference%2Fstats.sampling.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBaumgartenPatel2022" class="citation book cs1">Baumgarten, Christoph; Patel, Tirth (2022). "Automatic random variate generation in Python". <i>Proceedings of the 21st Python in Science Conference</i>. pp. 46–51. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.25080%2Fmajora-212e5952-007">10.25080/majora-212e5952-007</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Automatic+random+variate+generation+in+Python&rft.btitle=Proceedings+of+the+21st+Python+in+Science+Conference&rft.pages=46-51&rft.date=2022&rft_id=info%3Adoi%2F10.25080%2Fmajora-212e5952-007&rft.aulast=Baumgarten&rft.aufirst=Christoph&rft.au=Patel%2C+Tirth&rfr_id=info%3Asid%2Fen.wikipedia.org%3AInverse+transform+sampling" class="Z3988"></span></span> </li> </ol></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Inverse_transform_sampling&oldid=1244749103">https://en.wikipedia.org/w/index.php?title=Inverse_transform_sampling&oldid=1244749103</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Monte_Carlo_methods" title="Category:Monte Carlo methods">Monte Carlo methods</a></li><li><a href="/wiki/Category:Non-uniform_random_numbers" title="Category:Non-uniform random numbers">Non-uniform random numbers</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 8 September 2024, at 23:32<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Inverse_transform_sampling&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-qjjsx","wgBackendResponseTime":2113,"wgPageParseReport":{"limitreport":{"cputime":"0.299","walltime":"0.449","ppvisitednodes":{"value":1111,"limit":1000000},"postexpandincludesize":{"value":18904,"limit":2097152},"templateargumentsize":{"value":516,"limit":2097152},"expansiondepth":{"value":8,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":41454,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 235.226 1 -total"," 41.49% 97.587 4 Template:Cite_book"," 35.33% 83.108 1 Template:Short_description"," 21.61% 50.832 2 Template:Pagetype"," 9.86% 23.184 3 Template:Cite_journal"," 8.04% 18.923 2 Template:Main_other"," 7.13% 16.769 1 Template:SDcat"," 6.51% 15.309 4 Template:Cite_web"," 1.07% 2.517 1 Template:Short_description/lowercasecheck"]},"scribunto":{"limitreport-timeusage":{"value":"0.143","limit":"10.000"},"limitreport-memusage":{"value":4697945,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-4qzqr","timestamp":"20241122141356","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Inverse transform sampling","url":"https:\/\/en.wikipedia.org\/wiki\/Inverse_transform_sampling","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1377019","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1377019","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2002-03-23T12:26:42Z","dateModified":"2024-09-08T23:32:26Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/6\/68\/Inverse_transform_sampling.png","headline":"basic method for pseudo-random number sampling"}</script> </body> </html>

CINXE.COM

Inverse transform sampling - Wikipedia