What is an intractable integral? How do you recognize one?

[sarikan]

Greetings,
I've been using Bayesian methods and especially Gibbs sampling to work on models of various complexity, and I've always accepted the pretty much standard textbook explanation as a sensible justification for using sampling methods: sometimes the posterior distributions of Bayesian models may be intractable.

It occurred to me at one point that none of the resources I have properly explain what they mean by that. Google scholar search made me even more confused, since many works seem to use intractable to refer to "resource intensive calculation". Analytically intractable seems to be a better term I guess, but what that means exactly is not still clear to me.

How do you know a (multiple) integral is analytically intractable? Other than the obvious situations where -∞ and ∞ bounds, I mean. (Would this be intractable by the way?)

I'm looking for a proper discussion of the topic, preferably in a Bayesian inference context. It is amazin how many textbooks simply say "this integral may be interactable etc etc.. so let's use sampling"

Any pointers would be much appreciated

Kind regards
Seref

 

[sarikan]

Ok, I have to confess that I've been bitten by my lack of proper understanding of the word intractable. My native language is not English, and I've taken intractable as impossible to calculate, which was wrong.

I would still appreciate your input though, is not this term a bit subjective?

 

[frbl]

Ok, I have to confess that I've been bitten by my lack of proper understanding of the word intractable. My native language is not English, and I've taken intractable as impossible to calculate, which was wrong.

I would still appreciate your input though, is not this term a bit subjective?

Hi Sarikan,

I know this topic is over a year old, but just in case someone else is looking for this; I'm not a math expert at all, but I understand an integral being intractable when it is not possible to (more or less) track it down to the 'primary' set of functions. Primary in this case being the functions which you can derive to etc. (correct me if I'm wrong)

I'm not able to give an explanation on how you define a function to be intractable, but at least this might give some idea's. Here is an explanation

- frbl

 

[sarikan]

Hi frbl,
Thanks a lot for taking the time to respond to this. It is never too late for useful responses :)

 

[FactChecker]

Greetings,

How do you know a (multiple) integral is analytically intractable? Other than the obvious situations where -∞ and ∞ bounds, I mean. (Would this be intractable by the way?)

I don't think that ∞ bounds are the main problem. Some general examples can be found in http://www.stat.cmu.edu/~larry/=sml2008/lect2.pdf. But I think the general answer is this -- if you try to integrate it and cannot, then it is intractable (to you). Sampling techniques have their drawbacks, but they give you an alternative when the integral is too tough. And many integrals are too tough.