Everything that follows is with respect to some fixed target number of clues,
c.
We need to know how much worse Var(
M[1](
G)+...+
M[
r](
G) ) is than Var(
M(
G[1])+...+
M(
G[
r]) ) where:
- M[1,..,r](G) are the mimimals estimates from processing r independent subgrids of the same random solution grid.
- M(G[1]),...,M(G[r]) are the minimals estimates from processing r independent subgrids of r independent solution grids
OK, it's not great notation. But let's press on.
So, by the standard formula for the variance of sums: Var(
M[1](
G)+...+
M[
r](
G) ) =
r.Var(
M(
G)) +
r(
r-1).Cov(
M[1](
G),
M[2](
G))
whereas: Var(
M(
G[1])+...+
M(
G[
r]) ) =
r.Var(
M(
G)) because those terms are fully independent
and so the first is worse than the second by a factor of 1 + (
r-1).ε
where ε (epsilon) = Cov(
M[1](
G),
M[2](
G)) / Var(
M(
G)) .
Now the question is: what's that covariance? First some notation:
m(
g) is the true number of minimals for fixed solution grid
g;
m(
G) is the corresponding random variable when the solution grid is picked uniformly at random;
m is the average of
m(
g) for all
g. OK then:
- Cov( M[1](G), M[2](G) )
- = Expectation( (M[1](G)-m).(M[2](G)-m) )
- = Expectation( M[1](G).M[2](G) ) - m^2 because Expectation(M[1](G)) = Expectation(M[2](G)) = m
- = Sum_{g}( Prob(G=g).Expectation(M[1](g).M[2](g)) ) - m^2
- = Sum_{g}( Prob(G=g).m(g)^2 ) - m^2 because M[1](g) and M[2](g) are independent given g
- = Expectation(m(G)^2) - Expectation(m(G))^2
- = Var(m(G))
So epsilon, ε = Var(
m(
G)) / Var(
M(
G)), the ratio of the variance of the
actual number of minimals for a random solution grid to the variance of the
estimated number of minimals from a single subgrid of a random solution grid. In practice, most of the randomness of the
M(
G) variable comes from the
M part (it makes more difference what subgrid you pick than what solution grid you pick), so ε is much closer to 0 than to 1 and we can get away with non-trivial
r before any pain is felt in the variance.
)