Building probability distribution functions from observation
i am not sure i understand correctly what the question is or rather what are the observations from which the (experimental) distributions are going to be estimated.

The problem of a distribution estimation is related more to statistics than computer science althougn it can be relevant in this area as well.

There are various methods using 2 main approaches: 


Parametrized models of a probability distribution, where one (assuming prior knowledge) uses a pre-defined model (or form or function) of the distribution (e.g a Gaussian) with some free parameters depending on data (observations) and estimates these parameters (eg through Maximum Likelihood or EM algorithm or Maximum Entropy etc..). Even if the form of the prob distribution is not known this method can still be used on approximations like Gauusian Mixture Models. This method produces smooth (and usually robust) estimated distributions assuming the prior form is close to the underlying prob. distribution.
Un-parametrized models, estimate the whole PD (including its form) directly from the data. methods in this category are Parzen windows and kernel estimation. This method can be better from parametrized estimation provided the form of the underlying pdf is completely unknown or non-trivial or irregular in some sense.


All the previous methods are computationally efficient (although not necessarily polynomial). This is like the way the Simplex algorithm works, although it is not polynomial-time, it is efficient in many practical situations.