[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums

Variance Reduction

Posted By: Timothy Chow
Date: Saturday, 26 July 2014, at 8:14 p.m.

In Response To: Variance Reduction (rambiz)

rambiz wrote:

I know that Variance Reduction virtually increases the number of trials but I don't know by how much! I doubt there is a rigorous theory out there, which actually quantifies this effect. As long as no theory has been developed (or exposed to the public for proof-reading purposes), I am not going to put much confidence in all the confidence intervals reported by the bots.

Here is a technical fact that may give you some reassurance.

Suppose you take repeated independent samples of the same random variable X. We calculate the sample variance. What are the chances that the sample variance deviates significantly from the true variance?

This sort of situation is governed by Hoeffding's inequality. Provided that X is bounded, the probability that the sample value deviates from the true value by more than t after n trials is exponentially small in t and n. (Hoeffding's inequality is usually phrased in terms of the sample mean versus the true mean, but it applies to the sample variance too; just consider X 2 in place of X.)

In other words, you don't have to worry that the reported confidence interval is a poor approximation to the truth, provided two conditions are satisfied:

1. The samples are independent.

2. The luck is bounded.

Strictly speaking, these assumptions don't quite hold. Neil Robins's worry about the funny thing that XG does after 72 rollout trials is basically an observation that XG isn't averaging together independent samples. I'm not sure exactly what XG does, so it's possible that there is some systematic violation of independence that persists even after a large number of trials. My guess, however, is that it washes out after enough trials. (Note, by the way, that rotating the dice is also a violation of independence. But again, I don't think that this ends up being a problem in the long run.)

As for the luck (i.e., the number that you add to the equity estimate in order to get a variance-reduced result), in principle it could be unbounded. However, in practice it is always bounded by some small constant (say, 10), so this is again not a serious worry.

Note that Hoeffding's inequality does not assume that the variables are Bernoulli or that the normal approximation is a good approximation, so it is robust in that sense.

Messages In This Thread

 

Post Response
Your Name:
Your E-Mail Address:
Subject:
Message:

If necessary, enter your password below:

Password:
 

 

[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums is maintained by Stick with WebBBS 5.12.