# Monte Carlo estimator of the number of 1's in a very long binary sequence

Preface

The question below is related to a problem I am working on, which requires counting the number of times a logic-valued function evaluates "TRUE" given an input value. The size of my input set is HUGE and evaluating the function is rather costly. However, I can think of this statistically by viewing the set of values generated by applying the function to each input value as a population. I would like to study this population statistically by evaluating a (relatively) small subset of the input values and using that information to infer a plausible range for the total number of times it would have evaluated true had I actually evaluated each input.

Therefore, I chose to conceptualize this as inferring the total number of 1's in a very long binary string via Monte Carlo. This conceptualization contains all the salient features of my problem.

Problem Statement

Given a long (but finite) binary string, $S$ with $n_S\gg 2^{20}$ I would like to use a Monte Carlo sampling approach to estimate the number of 1's in S.

Probabilistically, if I let each digit in S have an equal chance of being selected by the Monte Carlo sampler, then the digits in S can be thought of as a outcomes of a random variable. Therefor, the goal is to estimate $\mu = E[x\in S]$ via Monte Carlo. Since we know the size of S, our estimate of the number of 1's in S will be $\mu n_S$. However, there is no explicit formula for calculating $\mu$ apart from brute force enumeration.

For very large sets, enumeration is not possible and the basic/naive Monte Carlo approach is very inefficient. I was thinking that some form of adaptive stratification would be helpful, with adaptation based on the sample average of each strata.

Any suggestions or references to relevant literature would be helpful.

• Can you expand on the method used to generate the string? This might be a good application for polynomial chaos techniques. Mar 18, 2014 at 3:53
• I am understanding that each bit in the string is the output of a boolean function. What does this function look like? Mar 18, 2014 at 15:48
• Right, but there are spectral expansion techniques wherein it could matter. For instance, it is possible to generate a million monte-carlo simulations of a dynamical system parameterized by a random parameter while only actually fully computing a handful of basis terms. Mar 18, 2014 at 16:14
• – user76844
Mar 18, 2014 at 17:45
• How accurate do you want to be? Mar 22, 2014 at 1:20

I propose the following:

Let $T$ be the estimated time of computation, and assume we want a precision such as the variance is fixed to a certain value $V$.

The size of the input is $n_s$, let us plit it in $m$ parts with equal sizes $n'_S$.

On the $k^{th}$ subpopulation, estimate the proportion $p_k$ with a naive estimator condidering only the $MC^k$ first digits: $$\hat{p_k}^{MC^k} =\frac1{MC^k} \sum_{a=1}^{MC^k} 1_{a^{th}\text{ digit = 1}}$$

You have an estimate of variance of $\hat{p_k}^{MC^k}$ given, assuming non correlation between 2 entries, by $$V_k^{MC^k}=\frac 1{{MC}^k} \hat{p_k}^{MC^k}(1-\hat{p_k}^{MC^k})$$

The whole estimator is $$\hat p(MC^1,\ldots,MC^m)= \frac 1{n_S} \sum n'_S\hat{p_k}^{MC^k} = \frac 1m\sum \hat{p_k}^{MC^k}$$

and an estimate of the variance is, considering that the subpopulations are uncorrelated: $$V(MC^1,\ldots,MC^m)= \frac 1{m^2} \sum \frac 1{{MC}^k}\hat{p_k}^{MC^k}(1-\hat{p_k}^{MC^k})$$

Now the optimization of $T = \sum MC^k$ under constrain $V(MC^1,\ldots, MC^m) = V$ gives the heuristic solution $$MC^k\propto \sqrt{\hat{p_k}^{MC^k}(1-\hat{p_k}^{MC^k})}$$

So here is the algorithm you could try:

• use a small fraction of your computation time to get a first estimate of each $V_k^{MC^k}$
• decide to manage your computation time according to the previous equation

You should get the theorical variance

$$V(MC^1,\ldots,MC^m)\propto \frac 1{m^2} \sum \sqrt{\hat{p_k}^{MC^k}(1-\hat{p_k}^{MC^k})} \\ \simeq \frac 1{m} \sqrt{p(1-p)}$$ which is a diminution of a factor $m$ compared to the variance of the naive estimator.

• thanks for your answer. I have a couple question about notation: What does $MC^k$ stand for, is it an exponent? Also, it seems like the various $\hat p_k$ are going to be correlated, since later $p_k$'s include data from earlier $p_k$'s based on your definition: $\hat{p_k}^{MC^k} =\frac1{MC^k} \sum_{a=1}^{MC^k} 1_{a^{th}\text{ digit = 1}}$ Also, could you show the steps in your optimization?
– user76844
Mar 24, 2014 at 13:31
• MCk is the number of tries in the kth substring. Mar 24, 2014 at 13:58
• the various p_k are not correlated, because in the sum the ath digit is the digit of the substring! Mar 24, 2014 at 15:43
• and eventually, for the optimization: this is just a regular Lagrange multipliers, assuming that the $\hat{p_k}$ are close to the value they estimate, and then that they do not depend on $MC^k$ at the first order. Mar 24, 2014 at 15:45
• Thanks, that's what I thought, but it wasn't explicit. Where did you learn about this algorithm...or did you make it up? It reads a lot like the algorithm I found here: hal.archives-ouvertes.fr/docs/00/19/30/41/PDF/propopt.pdf
– user76844
Mar 24, 2014 at 15:59

The following two up-to-date articles could also be interesting for you:

Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget: In this paper Markov chain Monte Carlo (MCMC) sampling is analysed by an adaptation of the Metropolis-Hastings (MH) algorithm reducing the computational budget. This is done by sequential hypothesis tests accepting or rejecting a sample based on small fractions of the data with high confidence.

An alternative approach is provided by An Adaptive Subsampling Approach for MCMC Inference in Large Datasets which is presented as more robust than the techniques above, but with the cost of increased computation.

• Thanks! Ill take a look at these as supplementary reading. MCMC is not directly related to my problem, as there is no associated likelihood function being developed (its an arbitary string of 1's and 0's that I am effectively "polling" via classical Monte Carlo). However, this information looks great so thanks again.
– user76844
Mar 24, 2014 at 18:01