//
you're reading...
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 <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/generate.h>
#include <thrust/sort.h>
#include <thrust/copy.h>
#include <thrust/unique.h>
#include <cstdlib>

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< (2<<20); n *=2){

    thrust::host_vector<int> hv(n);
    thrust::generate(hv.begin(), hv.end(), rand_functor(n));
    thrust::device_vector<int> dv = hv;
    thrust::sort(dv.begin(), dv.end());
    thrust::device_vector<int>::iterator newend =
       thrust::unique(dv.begin(),dv.end());
    int numunique = newend - dv.begin();
    printf("#bins %d  # distinct: %d  ratio %f\n",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

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: