7

Are there any good examples of a seemingly simple probability problem, which is actually intractable?

I am trying to motivate the use of simulation, and would like to come with an example of when it is necessary that is accessible. The hope being something like:

"Intuitively it seems easy enough to model the amount of aces left after a round of poker, but due to $x$, $y$ and $z$, this is actually infeasible to calculate analytically".

But I am struggling to find a good / simple example.

Any help would be appreciated.

Søren Emil Schmidt
  • 71
  • 1
  • 3
    This question appears rather broad, vague, and subjective: "Simple" in what sense? "Accessible" to whom? What exactly does "calculate analytically" mean? What constitutes a "good" example? Precisely how difficult is "infeasible"? For instance, if an approximation to 100 decimal places exists, but no theoretically exact closed formula exists, would that be "feasible" or not? – whuber May 26 '17 at 14:03
  • 3
    I don't have a reference off-hand, but my recollection is that Mark Kac thought of Monte Carlo because he was interested in finding the probability of winning a game of solitaire given a specific set of cards showing. The solution was, at least to him, combinatorialy intractable. I don't mean that last sentence in any derogatory sense. I just don't know whether or not in the 50 years since, someone has solved that problem analytically. – meh May 26 '17 at 14:31
  • I see I should have been more precise, my apologies @whuber. Simple in the sense that when hearing the problem, most people would think - "that should be possible to calculate rather easily, in a closed form, but when in reality it is necessary to either approximate it to 100 decimals, through simulation / numeric approximation. Basically a probabilistic problem that a student with some knowledge of probability would intuitively think to be "closed form solvable", when in reality it is intractable. Ah yes I remember reading that aginensky, that might be a good example, thank you. – Søren Emil Schmidt May 26 '17 at 14:53
  • 4
    Thank you for clarifying. I still find your criterion "a student with some knowledge of probability would intuitively think to be "closed form solvable", when in reality it is intractable" to be (highly) subjective. It makes your question one about the knowledge, training, and thought processes of hypothetical students rather than one about probability. Surely you can find easily accessible ways to motivate simulation. For instance, if your audience knows how to play the game of Monopoly, ask them about finding the chance of winning if they stick to one strategy and their opponents to another. – whuber May 26 '17 at 15:02
  • 3
    Surely, the "obvious" canonical answer is to compute $\mathbb{P}(Z \leq z)$ where $Z$ is standard normal. But, as @whuber alludes to, while it meets your stated criteria to a "t" including the fact that it is *provably* "intractable" (in a precise sense which this comment space is too small to contain), it does *not* follow that simulation (compared to numerical approximation) is the answer. :-) A slightly more serious answer is the computation of partition functions, which has generated a lot research interest in simulation methods over the years. – cardinal May 26 '17 at 18:55
  • 1
    The Bertrand paradox seems like a good candidate; it's commonly cited as an example of why sigma algebras are key to defining probabilities. Depending on how the students goes about conducting the simulation, they will obtain different results. There is no unique answer unless the meaning of "chosen at random" is specified. – Sycorax May 26 '17 at 22:27
  • 1
    One could make the argument that any problem for which Gibbs Sampling can be used fits this description: I could see it as seeming counter intuitive that $p(a | b, x)$, $p(b | a, x)$ could be in closed form, but $p(a|x)$ and $p(b|x)$ are not. – Cliff AB May 27 '17 at 00:04

3 Answers3

2

The survival function $S_{t}$ is a quantity of interest in many (most?) kinds of event history analysis. It is commonly estimated, and 'survival curves' depicting $S_{t}$ versus time are often used to compare the cumulative probability of events among different groups. Statistical comparisons are often facilitated by inference—things like hypothesis test and confidence intervals.

I and a few statisticians have struggled with several different approaches to provide an asymptotic analytic estimator of the sample variance of the survival function ($\sigma^{2}_{\hat{S}_{t}}$) in discrete time event history models (a la logit hazard, probit hazard, etc. models), which would be useful to construct hypothesis tests and confidence intervals.

It turns out that—as best I understand it—that while it is possible and common to estimate the asymptotic variance of sums of random variables (like the sample mean), the asymptotic variance of products of random variables is a tricky sticky wicket to estimate.

$$\hat{S}_{t} = \prod^{t}_{i=1}{1-\hat{h}_{i}}$$

where $\hat{h}_{t}$ is the discrete time hazard function at time $t$.

We have more or less given up on an asymptotic estimator of the variance of that puppy, and declared that numerical techniques like bootstrapping seem to be our best bets.

Alexis
  • 26,219
  • 5
  • 78
  • 131
0

You've got 5 variables and you're doing a "multivariate" analysis. You assume multivariate normality and enjoy a complete data set. Then the maximum likelihood estimates of the mean and covariance matrix are closed form and easy to calculate.

Oh wait, you didn't want to assume joint normality. You meant to assume that, marginally, each of your variables follows a beta distribution. No big deal. There must be a multivariate analogue of the beta distribution with an arbitrary correlation structure, right? Well, you might be able to construct something, but I'll call it "intractable" for my level of patience. Here is a reddit post from someone trying to figure out something similar without much luck.

Ben Ogorek
  • 4,629
  • 1
  • 21
  • 41
0

A simple probability problem that is intractable could be the following for a horse race.

If the horse trainer has a win rate of 25% and the jockey a 10% win rate and the horse has a 40% win rate what is the un-normalised probabilty of success of the horse in today's race?

The trainer has trained the horse to have a 40% success rate but will the rate fall in future races towards 25%? Will the jockey have a better chance than 15%, and by how much, on a horse that wins 40% of the time and a trainer that wins 25% of the time?

robert
  • 96
  • 1