Approaches for Theoretical Analysis of Estimates of Probability Distributions Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers that theoretically analyze and bound the estimate?

As a more concrete example, consider this paper which designs a streaming algorithm to estimate the degree distribution of a graph and defines a new notion of closeness called Relative-Hausdorff Distance (RHD). The paper experimentally validates their estimate to be close (according to RHD) to the actual distribution for several real-world graphs. I want to know if there are methods/references in literature that one can use to give provable (theoretical) guarantees of their closeness.
Disclaimer: I am biased, in that I will suggest a survey which I have written.



What you seem to be looking for can be captured under the field of distribution testing, a subfield of Property Testing initiated in TCS by the work(s) of Batu, Fortnow, Rubinfeld, Smith, and White in 2000. 

Most of the works in this field answers questions of the following sort:


  Given i.i.d. sample from one (or several) unknown propbability distribution(s) over a known discrete domain, and a parameter $\varepsilon &gt; 0$, how to distinguish between (i) the distribution has some prespecified property of interest $\mathcal{P}$ and (ii) it is at distance at least $\varepsilon$ (in total variation distance/statistical distance/$\ell_1$ distance) from every distribution that has this property?


For instance, defining the property to be the singleton $\{p\}$ (where $p$ is a known, fixed distribution of interest) you get the identity testing problem.

People have considered many variants, including varying the metric ($\ell_2$, Hellinger, Earthmover, $f$-divergences). It dates back to last year, but here is a list of references (from the second survey below).

There has been a lot of work in this area: I would suggest the following pointers and surveys:


Chapter 11 of the upcoming Introduction to Property Testing book by O. Goldreich
A Survey on Distribution Testing: Your Data is Big. But is it Blue?
(C. Canonne, 2015)
http://eccc.hpi-web.de/report/2015/063/
Taming Big Probability Distributions (R. Rubinfeld, 2012)
https://people.csail.mit.edu/ronitt/papers/xrds-rr-dist.pdf


(There are others -- see e.g. the surveys referenced by Ronitt Rubinfeld here for property testing in general, and some discussion of distribution testing.)

Some slides:
http://www.cs.columbia.edu/~ccanonne/files/talks/candidacy-2015-04-20-columbia.pdf



Now, this is trying to address the question "after coming up with a (set of) hypotheses, how to test whether they are good. (Hence the testing and tolerant testing focus.) You may also want to start from the start, and ask how to learn the distribution itself, or the relevant parameter (i.e., learning instead of testing). Not surprisingly, this becomes distribution learning (or density estimation), with all its variants (proper learning, agnostic learning, etc.). I am a bit more out of my depth there, but if that's what you are after you may want to have a look at


Learning Structured Distributions (I. Diakonikolas, 2016)
Invited Book Chapter, Handbook of Big Data, Chapman and Hall/CRC.
http://www.iliasdiakonikolas.org/distribution-learning-survey.pdf 


and things like this (slightly outdated) workshop from STOC'12.