Existe-t-il une distribution univariée à partir de laquelle nous ne pouvons pas échantillonner?

Nous avons une grande variété de méthodes de génération aléatoire à partir de distributions univariées (transformation inverse, acceptation-rejet, Metropolis-Hastings, etc.) et il semble que nous pouvons échantillonner à partir de n'importe quelle distribution valide - est-ce vrai?

Pourriez-vous fournir un exemple de distribution univariée impossible à générer de manière aléatoire? Je suppose que cet exemple où il est impossible n'existe pas (?), Alors disons que par "impossible", nous entendons également des cas qui sont très coûteux en calcul, par exemple qui nécessitent des simulations de force brute comme le dessin d'énormes quantités d'échantillons pour accepter juste un peu d'entre eux.

Si un tel exemple n'existe pas, pouvons-nous réellement prouver que nous pouvons générer des tirages aléatoires à partir de n'importe quelle distribution valide? Je suis simplement curieux de savoir s'il existe un contre-exemple pour cela.

Si vous connaissez la fonction de distribution cumulative, , vous pouvez l'inverser, que ce soit analytiquement ou numériquement, et utiliser la méthode d'échantillonnage à transformation inverse pour générer des échantillons aléatoires https://en.wikipedia.org/wiki/Inverse_transform_sampling .$F(x)$

Définissez . Cela gérera toute distribution, qu'elle soit continue, discrète ou toute combinaison. Cela peut toujours être résolu numériquement, et peut-être analytiquement. Soit U un échantillon d'une variable aléatoire distribuée comme Uniforme [0,1], c'est-à-dire d'un générateur de nombres aléatoires [0,1] uniforme. Alors F - 1 ( U ) , défini comme ci-dessus, est un échantillon aléatoire d'une variable aléatoire ayant la distribution F ( x ) . $F^{-1}(y) = inf(x:F(x) \ge y)$$F^{-1}(U)$$F(x)$

Ce n'est peut-être pas le moyen le plus rapide de générer des échantillons aléatoires, mais c'est un moyen, en supposant que F (x) est connu.

Si F (x) n'est pas connu, alors c'est une autre histoire.

Lorsqu'une distribution n'est définie que par sa fonction de génération de moment ou par sa fonction caractéristique Φ ( t ) = E [ exp { i t X } ] , il est rare de trouver des moyens de générer à partir de ces distributions.$\phi(t)=\mathbb{E}[\exp\{tX\}]$$\Phi(t)=\mathbb{E}[\exp\{itX\}]$

Un exemple pertinent est constitué de distributions stables$\alpha$ , qui n'ont pas de forme connue pour la densité ou le cdf, pas de fonction de génération de moment, mais une fonction caractéristique de forme fermée.

Dans les statistiques bayésiennes, les distributions postérieures associées à des probabilités intraitables ou simplement à des ensembles de données trop volumineux pour tenir dans un ordinateur peuvent être considérées comme impossibles à (exactement) simuler.

$F$$u \sim (0,1)$$F^{-1}(u)$$F$$F^{-1}$

${\bf \theta} = (\theta_1,...,\theta_d)$$\theta_j$

Il existe des méthodes d'échantillonnage approximatif de cette partie postérieure dans certains cas, mais aucune méthode générale exacte n'existe pour le moment.

$(q_i)_{i=1}^\infty$$P(X=q_i)=0$$i$$\sum_{i=1}^\infty P(X=q_i)=0$$P(X\in \mathbb{Q})=1$

$\mu$$\pi(\mu) = 1$

Pourriez-vous fournir un exemple de distribution univariée impossible à générer de manière aléatoire?

$c$$c$

Si vous souhaitez uniquement échantillonner des variables aléatoires dont les valeurs peuvent être raisonnablement approximées par des nombres à virgule flottante 64 bits, ou si vous avez une tolérance similaire pour les erreurs finies dans la valeur, et que vous ne représentiez pas vos échantillons sur des machines de Turing de toute façon , considère ceci:

$X \sim \text{Ber}(p)$$p = 1 - c$$0$$1$

$0$$(-∞, c)$$1$$[c, ∞)$$0$$(-∞, 0)$$c$$[0, 1)$$1$$[1, ∞)$$c$$x$$y$-axe. Je ne sais pas ce qui rend l'échantillonnage le plus difficile, alors choisissez celui que vous (dés) aimez le plus ;-)

disons que par "impossible", nous entendons également les cas qui sont très coûteux en calcul, par exemple qui nécessitent des simulations par force brute comme le prélèvement d'énormes quantités d'échantillons pour n'en accepter que quelques-uns.

Dans ce cas, une réponse évidente semble évidente:

• $n$$n$
• Échantillonnez les pré-images d'une fonction de hachage cryptographique (c'est-à-dire générer du bitcoin et casser git et mercurial).
• Échantillonnez l'ensemble des stratégies de Go optimales (avec les règles chinoises de superko, qui rendent tous les jeux finis - si je comprends bien).

Un peu plus formellement: je vous donne une grande instance d'un problème NP-complet (ou EXP-complet, etc.) et je vous demande d'échantillonner uniformément l'ensemble de solutions pour moi.

$\bot$$\mathbb{R}$$-1$$\bot$

Vous pouvez facilement vérifier si une affectation de vérité donnée satisfait mon instance SAT, et après les avoir vérifiées, vous savez si l'une d'entre elles le fait, j'ai donc spécifié un CDF en vous donnant une formule booléenne (ou un circuit), mais pour échantillonner la distribution correspondante vous devez essentiellement devenir quelque chose d'au moins aussi puissant qu'un oracle de solvabilité SAT.

Je vous ai donc donné un nombre non calculable qui devrait jeter du sable dans vos engrenages, et je vous ai donné un CDF lent à calculer. Peut-être que la prochaine question évidente à poser est quelque chose comme ceci: y a-t-il un CDF représenté sous une forme efficace (par exemple, peut être évalué en temps polynomial) de sorte qu'il est difficile de générer des échantillons avec cette distribution? Je ne connais pas la réponse à celle-là. Je ne connais pas la réponse à celle-là.