2
$\begingroup$

Estimating $E[X]$ from i.i.d. copies $X_1,X_2,\dotsc$ of a random variable $X$ with unknown distribution $P$ is well studied, obviously. When $X$ has extremely large variance, the Monte Carlo estimates $$ \frac 1 n \sum_{j \le n} X_j $$ will generally not have low enough variance to be useful in practice. Moreover, one cannot give any quantitative bounds on the accuracy of such estimates (even merely with high probability) without further assumptions.

The problem seems to be made much easier if we're willing to say that we don't care about extreme events. One way to formalize this is to say that we're actually interested in estimating $E[X;A]=E[X \,1_A]$ for some set $A$ such that $P(A)$ is large. (Alternatively, we may want a confidence interval.) We may even be willing to choose $A$ to make the problem easier. (This relaxation of the problem is obviously not appropriate in all situations, but it does seem appropriate in the situation that led us to ask this question.)

At this stage, we're curious to hear about related work. The attack we're considering is to use basic facts about order statistics, but we don't want to reinvent the wheel.

Improve this question
$\endgroup$
5
  • $\begingroup$ If $A$ represents a quantile range not containing 0 or 1, then $A$ is a bounded interval. In that situation, one can apply, e.g., Hoeffding's inequality to get an exponentially-tight estimate of the rate of convergence to $E[X;A]$. On the other hand, $E[X]$ and $E[X;A]$ need not bear much resemblance to each other (i.e., for any fixed $A$ and with sufficiently large variance, the expectations can differ by arbitrarily large amounts). $\endgroup$
    – Bill Bradley
    Commented Jun 5, 2016 at 1:30
  • $\begingroup$ What is the application you have in mind, the context for the requirement of "useful in practice"? The trivial answer is "for every P, for every level of confidence, there is some n...", but in context there might be something non-trivial to say. $\endgroup$
    – user44143
    Commented Jun 5, 2016 at 1:31
  • $\begingroup$ @BillBradley: Yes, but $P$ is unknown and so you do not know the quantile range. It's not immediately obvious how to modify the standard estimator to target $E[X;A]$ instead of $E[X]$... or perhaps one can simply analyze the standard estimator as an estimator for $E[X;A]$. We've thought about Hoeffding. You can consider the fact that, with probability $1-2\epsilon$, independently, each sample will be in the $(\epsilon,1-\epsilon)$ quantile range, and so you can then apply Hoeffding conditionally on the event that the sample is entirely in some desired range. Is that what you have in mind? $\endgroup$
    – D.R.
    Commented Jun 5, 2016 at 2:07
  • $\begingroup$ @MattF: The situation we have in mind is one where you are trying to estimate a divergence between a pair of distributions... think KL divergence. The KL divergence can be dominated by what happens in the tail. But it might be reasonable to be more concerned with the log of the Radon--Nikodym derivative at points that are "typical", rather than in the tails. $\endgroup$
    – D.R.
    Commented Jun 5, 2016 at 2:08
  • $\begingroup$ Ah, I see. So you have something in mind like: take $N$ samples, compute the (empirical) interquartile range, then compute the expectation within that range. Order statistics will give you the (beta-)distributions for the actual quantile range, so for large $N$ you can be pretty confident that $P(A)$ is about 1/2. If your underlying distribution is continuous, this seems reasonable; if your distribution contains atoms, then even asymptotically you can have problems. Consider $P(0)=1/2, P(-x)=P(x)=1/4$; for large $x$, this suffers from variance much like the original Monte Carlo case. $\endgroup$
    – Bill Bradley
    Commented Jun 8, 2016 at 10:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .