4

For many people I know, they do not think sampling from a given distribution is a hard problem in general. For example, many software provide functions do to sample from normal distribution or uniform distribution.

How can I teach to other person that, in general, sampling is hard (in terms of time complexity), which is why we have many algorithms to do sample, such as McMC? Is there any good intuitive example of to show sampling is a non-trivial problem?

Haitao Du
  • 32,885
  • 17
  • 118
  • 213
  • You'll have to bring up the example, that's the only way to show that something's difficult. Bring up a case where there is not analytical expression, and you have to do MCMC, for instance. – Aksakal Feb 28 '18 at 18:50
  • @Aksakal thanks for the comment. Do you have couple of examples to show sampling is not trivial? I am thinking about some examples from rejection sampling, that trying to say, if we sample for P(Y|X) is hard, if we conditional on something almost never happen. – Haitao Du Feb 28 '18 at 18:55
  • In "deep learning" by Goodfellow, Bengio & Courvile there is a nice observation in the context of generative models that is relevent to sampling too. They say that if your target is a set of cats & dogs, you should play on to levels. First, your items should represent well a cat (or a dog). Other than that, you should generate/sample both cats and dogs, as in the target. Producing only excellent cats won't be enough. I think that this example can help someone understand that there are more constraints to the problem than it seems first. – DaL Mar 01 '18 at 07:53

1 Answers1

4

How about the following distribution on variables $x_i \in \texttt{ascii}$:

$P(x_i ... x_k) = 0$ if $x_1x_2\ldots x_k$ is not a valid program in C (or your favorite formal language)

$P(x_i ... x_k) \propto w^{-1}$ otherwise, where $w$ is the number of characters $x_i$ which are not spaces.

I think this is a reasonable example because

  1. It's fairly interpretable: Sample random C programs inversely proportional to their (non whitespace) length.

  2. There is no trivial solution -- simply sampling valid programs is nontrivial. Rejection sampling is also hard, since most of the mass lies with in a small number of programs. Computing the partition function is also intractable for moderate values of $k$.

  3. An MCMC approach seems feasible in this case. There are many reasonable proposal distributions. Although the mixing time might be huge.

shimao
  • 22,706
  • 2
  • 42
  • 81
  • I liked your example very much (+1), however, I cannot think about a MCMc method on this, could you tell me more about it? – Haitao Du Feb 28 '18 at 21:09
  • 1
    Yes, we can use metropolis-hastings where we sample from the proposal distribution by randomly picking one $j \in 1 \ldots k$ and then replacing $x_j$ with a new character at random. This proposal distribution is symmetric. Start off the chain with a simple hello world program. – shimao Feb 28 '18 at 21:27