//
Uncategorized

# Testing Thrust with simple Monte Carlo Experiment to compute 1-1/e

If we throw n balls randomly into n bins, what fraction of the bins are occupied?

The probability that a given bin is missed by all n balls is

{1 – 1/n) ^ n

which we know from calculus approaches 1/e. So the expected number of such _missed_ bins approaches n/e, as n gets large. Hence the fraction of _occupied_ bins as n grows is expected to be simply 1- 1/e = 0.632120559…., or about 63%.

Here is thrust code to demonstrate this fact using a series of Monte Carlo experiments with various bin sizes….

```#include &lt;thrust/host_vector.h&gt;
#include &lt;thrust/device_vector.h&gt;
#include &lt;thrust/generate.h&gt;
#include &lt;thrust/sort.h&gt;
#include &lt;thrust/copy.h&gt;
#include &lt;thrust/unique.h&gt;
#include &lt;cstdlib&gt;

struct rand_functor
{
const int a;

rand_functor(int _a) : a(_a) {}

__host__ __device__
int  operator()() const {
return rand() % a;
}
};

int main(void)
{
for (int n =2; n&lt; (2&lt;&lt;20); n *=2){

thrust::host_vector&lt;int&gt; hv(n);
thrust::generate(hv.begin(), hv.end(), rand_functor(n));
thrust::device_vector&lt;int&gt; dv = hv;
thrust::sort(dv.begin(), dv.end());
thrust::device_vector&lt;int&gt;::iterator newend =
thrust::unique(dv.begin(),dv.end());
int numunique = newend - dv.begin();
printf(&quot;#bins %d  # distinct: %d  ratio %f\n&quot;,n, numunique,  double (numunique) / n);
}
return 0;
}
```

Output:

#bins 2 # distinct: 2 ratio 1.000000
#bins 4 # distinct: 2 ratio 0.500000
#bins 8 # distinct: 5 ratio 0.625000
#bins 16 # distinct: 12 ratio 0.750000
#bins 32 # distinct: 18 ratio 0.562500
#bins 64 # distinct: 36 ratio 0.562500
#bins 128 # distinct: 79 ratio 0.617188
#bins 256 # distinct: 163 ratio 0.636719
#bins 512 # distinct: 323 ratio 0.630859
#bins 1024 # distinct: 654 ratio 0.638672
#bins 2048 # distinct: 1291 ratio 0.630371
#bins 4096 # distinct: 2602 ratio 0.635254
#bins 8192 # distinct: 5154 ratio 0.629150
#bins 16384 # distinct: 10319 ratio 0.629822
#bins 32768 # distinct: 20801 ratio 0.634796
#bins 65536 # distinct: 41388 ratio 0.631531
#bins 131072 # distinct: 82811 ratio 0.631798
#bins 262144 # distinct: 165811 ratio 0.632519
#bins 524288 # distinct: 331535 ratio 0.632353
#bins 1048576 # distinct: 663439 ratio 0.632705