Existe alguma distribuição univariada da qual não podemos provar?

12

Temos uma grande variedade de métodos para geração aleatória a partir de distribuições univariadas (transformação inversa, aceitação-rejeição, Metropolis-Hastings etc.) e parece que podemos amostrar literalmente qualquer distribuição válida - isso é verdade?

Você poderia fornecer algum exemplo de distribuição univariada impossível de gerar aleatoriamente? Eu acho que o exemplo onde é impossível não existe (?), Então vamos dizer que por "impossível" queremos dizer também casos que são muito computacionalmente caro, por exemplo, que as simulações de força bruta necessidade como a tiragem de enormes quantidades de amostras para aceitar apenas um alguns deles.

Se esse exemplo não existir, podemos realmente provar que podemos gerar sorteios aleatórios a partir de qualquer distribuição válida? Estou simplesmente curioso se existe um contra-exemplo para isso.

Tim
fonte
6
Realmente se resume ao que você quer dizer com "não posso / impossível", eu acho. Há casos em que o cdf e o pdf são muito caros para avaliar, por exemplo, o que tornaria a maioria dos métodos proibitivos, e não é difícil criar formas de distribuição em que bons limites de envelope no pdf (para uma aceitação-rejeição que evita principalmente a avaliação da função) não estão prontamente disponíveis. Portanto, falharia no caso de você já excluir e poderíamos tornar ainda mais caro (por desvio, em média) calcular do que usar accept-rejeitar (o que excluiria a tentativa de usar a inversão numérica do cdf)F
Glen_b -Reinstate Monica
3
Não podemos extrair amostras aleatórias uniformes do conjunto de números irracionais no intervalo (0,1) usando um computador. A prova é deixada como um exercício para o leitor.
Cliff AB
2
@Cliff AB Isso pode ser tratado por aritmética de intervalo. Defina um (o menor) intervalo em torno de cada ponto avaliável (racional) do computador, de modo que a totalidade de [0,1] seja coberta por esses intervalos. Para cada desenho "uniforme" avaliável por computador, avalie o intervalo inverso (com arredondamento externo) da função de distribuição cumulativa nesse argumento de intervalo. Isso produzirá uma amostra de intervalo da variável aleatória, 100% garantida para conter a amostra verdadeira.
27616 Mark L. Stone
2
O que eu entendo é que, já que você considera a rejeição suficientemente ineficiente como "impossível", se você considerar caro o suficiente para que qualquer outra abordagem conhecida seja pior (requer mais cálculo), provavelmente você também consideraria essas "impossíveis". Construindo cara-a-avaliar de F e F de que não é difícil, e torná-los para que maneiras óbvias de evitar realmente cálculo seja maior parte do tempo é também ineficiente parece ser possível ,,, CTD
Glen_b -Reinstate Monica
1
ctd ... (mas coletivamente, as pessoas são bastante engenhosas, então o que parece muito difícil um dia pode ser possível se você tiver uma boa idéia que contorne a maior parte do problema). Se dissermos que "a aproximação de tal e tal precisão é boa", muitas dessas dificuldades podem ser contornadas em muitos casos (por exemplo, é possível construir grandes tabelas de pesquisa / geração de histogramas, por exemplo, que na maioria das vezes você gera valores aproximados razoavelmente rápido).
Glen_b -Reinstala Monica

Respostas:

15

Se você conhece a função de distribuição cumulativa, , pode invertê-la, analítica ou numericamente, e usar o método de amostragem por transformação inversa para gerar amostras aleatóriashttps://en.wikipedia.org/wiki/Inverse_transform_sampling.F(x)

Defina . Isso manipulará qualquer distribuição, seja contínua, discreta ou qualquer combinação. Isso sempre pode ser resolvido numericamente e talvez analiticamente. Seja U uma amostra de uma variável aleatória distribuída como Uniforme [0,1], isto é, de um gerador de números aleatórios uniforme [0,1]. Então F - 1 ( U ) , definida como acima, é uma amostra aleatória de uma variável aleatória com distribuição F ( x ) . F1(y)=inf(x:F(x)y)F1(U)F(x)

Esta pode não ser a maneira mais rápida de gerar amostras aleatórias, mas é uma maneira, presumindo que F (x) seja conhecido.

Se F (x) não for conhecido, é uma história diferente.

Mark L. Stone
fonte
2
Se não é conhecido, então o que é conhecido? Obviamente isso é relevante. Se você não sabe nada, não poderá fazer nada. Se você sabe alguma coisa, depende do que é essa coisa.F(x
27616 Mark L. Stone
@ Tim Na verdade, é bastante comum não conhecermos F (X), mas podemos gerar amostras a partir dele. Esse é um cenário típico na simulação de Monte Carlo (estocástica).
Mark L. Stone
@ Tim: Se você não está interessado nesta história, não está claro em que história está interessada. Em resposta ao comentário de Glen_b, você disse que não estava preocupado com a amostragem ineficiente. Esse método, embora ineficiente, permitirá que você faça uma amostra de qualquer pdf (supondo que não seja tão mal-comportado que a integração numérica falhe, mas acho que ninguém se importa em usar essas distribuições). Portanto, a menos que você esteja interessado em, digamos, distribuições descontínuas em um número infinito de lugares, esta deve ser a resposta para sua pergunta: sim, podemos.
Cliff AB
Na verdade, se é conhecido, mas não F - 1 , isso é um problema. FF1
Xian
1
Depende do que você quer dizer com problema. Se é conhecido, então, pela minha resposta, F - 1 ( y ) = i n f ( x : F ( x ) y ) está sempre bem definido e pode ser resolvido numericamente. Pode não ser tão rápido quanto você gostaria, então se é isso que você quer dizer com problema, ok Se não é isso que você quer dizer, qual é o problema? FF1(y)=inf(x:F(x)y)
Mark L. Stone
7

Quando uma distribuição é definida apenas por sua função geradora de momentos ou por sua função característica Φ ( t ) = E [ exp { i t X } ] , é raro encontrar maneiras de gerar a partir dessas distribuições.ϕ(t)=E[exp{tX}]Φ(t)=E[exp{itX}]

Um exemplo pertinente é feito de distribuições -STABLEα , que não têm conhecidos forma para a densidade ou CDF, nenhuma função de geração de momento, mas uma função característica de forma fechada.

Nas estatísticas bayesianas, as distribuições posteriores associadas a probabilidades intratáveis ​​ou simplesmente conjuntos de dados grandes demais para caber em um computador podem ser vistas como impossíveis (exatamente) de simular.

Xi'an
fonte
Se você conhece apenas a função de geração de momento, pode usar a aproximação do ponto de sela e simular a partir dela.
Kjetil b halvorsen
1
@Xi'an You left out the word "efficiently". In the worst case, you can numerically invert the numerical inversion of the transform. That will do the job, maybe not "efficiently", but it will do it.
Mark L. Stone
3
@kjetilbhalvorsen: the saddlepoint approximation is the solution proposed in the link I put. But it is an approximation!
Xi'an
2

Assuming you refer to continuous distributions. By using the probability integral transform, you can simulate from any univariate distribution F by simulating u(0,1) and then taking F1(u). So, we can simulate a uniform, then that part is done. The only thing that may preclude the simulation from F is that you cannot calculate its inverse F1, but this has to be related to computational difficulties, rather than something theoretical.

Conti
fonte
1

Now that your question evolved into "difficult to sample from", just take any model with an intractable likelihood, assign a prior distribution to the model parameters θ=(θ1,...,θd), and suppose that you are interested in the marginal posterior distribution of one of the entries θj. This implies that you need to sample from the posterior, which is intractable due to the the intractability of the likelihood.

There are methods to approximately sample from this posterior in some cases, but no exact general method exists at the moment.

Noah
fonte
...but the question is about univariate distributions. There are lots of examples of complicated models where MCMC fails to converge even after enormous number of iterations.
Tim
@Tim And that's exactly why I said marginal posterior, which means univariate ... It seems to me you do not have clear what you are asking. The first two answers are clear in that theoretically, it is possible to sample from any distribution provided you know it.
Noah
1
I vote to put this question [ON HOLD] until the OP clarifies what he is asking and stop changing the question every time a new answer appears in order to make the answers inapplicable.
Noah
I am not changing my question "every time a new answer appears" ... Obviously statistical model with likelihood and prior is not univariate since it is declared in terms of conditional distribution. It is univariate if you sample from the posterior, but then I guess that you assume that we already have the marginal distribution so there is no problem with intracable posterior.
Tim
1
You confuse marginal with univariate, when those two notions have no connection. Univariate means the random variable is in R, while marginal means the distribution can be represented as an integral against another density. Actually, using this integral representation means a univariate rv can be simulated by first simulating a multivariate rv.
Xi'an
1

Not sure if this is really an answer ... I am guessing (but do not know) that one cannot sample from an only finitely additive distribution. An example would be the uniform distribution on the rational numbers, which only can exist as a finitely additive distribution. To see this, let (qi)i=1 be an enumeration of the rationals. Since the distribution is uniform, P(X=qi)=0 for any individual i, so i=1P(X=qi)=0 but P(XQ)=1.

If this answer looks strange and even irrelevant, look at more practical examples which are sometimes used in Bayesian inference: A uniform prior distribution on a real parameter, such as the mean of a normal distribution, say μ. That can be modeled by a "density" (not a real probability density) which is identically one: π(μ)=1. Such a prior can be used in Bayesian analysis (and is sometimes used, see the classic book by Box & Tiao), but we cannot sample from it. And, the probability distribution defined that way is only finitely additive, which you can see by an argument similar to the rational number example above.

kjetil b halvorsen
fonte
0

Você poderia fornecer algum exemplo de distribuição univariada impossível de gerar aleatoriamente?

Deixei cser constante do Chaitin , e provar o (distribuição do) variável aleatória que é constantementec.

Se você está interessado apenas em amostrar variáveis ​​aleatórias cujos valores podem ser razoavelmente aproximados por números de ponto flutuante de 64 bits, ou se você tem alguma tolerância semelhante a erros finitos no valor e não representava suas amostras como máquinas de Turing de qualquer maneira , considere isto:

Deixei XBer(p) com p=1-ce tente provar. Os valores0 0 and 1 are perfectly representable (in e.g. 64 bit floats with no error), but I think you'll generate them at incorrect frequencies unless you solve the halting problem.

The two CDFs are piecewise constant: one is 0 on (,c) and 1 on [c,). The other is 0 on (,0), then c on [0,1) and 1 on [1,). That is, one makes c relevant on the x-axis, the other on the y-axis. I'm not sure which makes sampling most difficult, so pick the one you (dis)like the most ;-)

let's say that by "impossible" we mean also cases that are very computationally expensive, e.g. that need brute-force simulations like drawing huge amounts of samples to accept just a few of them.

In this case, obvious answer seems obvious:

  • Sample uniformly the prime factors of n where n is large (i.e. break RSA).
  • Sample the preimages of a cryptographic hash function (i.e. generate bitcoin and break git and mercurial).
  • Sample the set of optimal Go strategies (with Chinese superko rules, which make all games finite—as far as I understand).

A bit more formally: I give you a large instance of an NP-complete problem (or EXP-complete, etc.) and ask you to uniformly sample the set of solutions for me.

Probably I should accept as a solution to no-instances (and no-instances only, and it would be the only solution). I should also come up with a bijection between e.g. integers (assuming you want to sample members of R) and solutions—which is often fairly trivial, just treat base 2 representations as truth assignments for my SAT instance, for example, and maybe use 1 to represent .

You can easily check whether any given truth assignment satisfies my SAT instance, and having checked them all you know whether any one does, so I have fully specified a CDF by giving you a boolean formula (or circuit), yet to sample the corresponding distribution you have to essentially become something at least as powerful as a SAT-solvability oracle.


So I gave you an uncomputable number which should throw sand in your gears, and I gave you a CDF that's slow to calculate. Maybe the next obvious question to ask is something like this: is there a CDF represented in some efficient form (e.g. can be evaluated in polynomial time) such that it's hard to generate samples with that distribution? I don't know the answer to that one. I don't know the answer to that one.

Jonas Kölker
fonte