Monte Carlo Sims - Please Check My Algorithm

Question

Basically the problem mimics the following:

There is an urn with 50 green balls and 50 red balls.

I am allowed to select balls from the urn without replacement with the following rules: for each red ball I lose a dollar, for each selected green ball I get a dollar.

I can stop the collection when I want. In the worst case, I select all 100 and net 0.

The question is to develop an optimal stop strategy and create a program to calculate the expected value of the strategy.

My strategy is to continue collecting the balls, while the expected value of choosing another ball is positive.

That is, the stop rule is DYNAMIC.

In latex, here is a recursive formula in the image:

http://i.stack.imgur.com/fnzYk.jpg

#include <stdio.h> #include <math.h> #include <stdlib.h> double ExpectedValue(double, double); double max(double, double); main() { double g = 50; double r = 50; double EV = ExpectedValue(g, r); printf ("%f\n\n", EV); system("PAUSE"); } double ExpectedValue(double g, double r){ double p = (g / (g + r)); double q = 1 - p; if (g == 0) return r; if (r == 0) return 0; double E_gr = max ((p * ExpectedValue (g - 1, r)) + (q * ExpectedValue (g, r - 1)), (r - g)); return E_gr; } double max(double a, double b){ if (a > b) return a; else return b; } 

I skipped it for 30 minutes and it still worked. For small values ​​of g and r, the solution is calculated very quickly. What am I doing wrong?

Any help is much appreciated!

Answer 1

Your algorithm is fine, but you are wasting information. For a specific pair (g, r) you calculate its ExpectedValue, and then you delete that information. Often, using recursion algorithms that remember previously calculated values, you can speed it up to LOT .

The following code runs in no time. For example, for g = r = 5000 it calculates 36.900218 in 1 second. He remembers previous calculations by ExpectedValue(g, r) to prevent unnecessary recursion and recounting.

 #include <stdio.h> #include <stdlib.h> double ExpectedValue(int g, int r, double ***expectedvalues); inline double max(double, double); int main(int argc, char *argv[]) { int g = 50; int r = 50; int i, j; double **expectedvalues = malloc(sizeof(double*) * (g+1)); // initialise for (i = 0; i < (g+1); i++) { expectedvalues[i] = malloc(sizeof(double) * (r+1)); for (j = 0; j < (r+1); j++) { expectedvalues[i][j] = -1.0; } } double EV = ExpectedValue(g, r, &expectedvalues); printf("%f\n\n", EV); // free memory for (i = 0; i < (g+1); i++) free(expectedvalues[i]); free(expectedvalues); return 0; } double ExpectedValue(int g, int r, double ***expectedvalues) { if (g == 0) return r; if (r == 0) return 0; // did we calculate this before? If yes, then return that value if ((*expectedvalues)[g][r] != -1.0) return (*expectedvalues)[g][r]; double p = (double) g / (g + r); double E_gr = max(p * ExpectedValue(g-1, r, expectedvalues) + (1.0-p) * ExpectedValue(g, r-1, expectedvalues), (double) (rg)); // store value for later lookup (*expectedvalues)[g][r] = E_gr; return E_gr; } double max(double a, double b) { if (a > b) return a; else return b; } 

Answer 2

In my opinion, the correct, but rather simple solution.

Here is what you can do:

• Eliminate recursion!
• Eliminate ExpectedValue
• Parallel code
• Read this [lecture notes] . It will definitely be helpful.

I can provide some sample code, but that would be dishonest.

Answer 3

Roughly speaking, adding one ball to the ballot box doubles the number of calls you will need to make to ExpectedValue (take your time on the boundary conditions). This is called O (e ⁿ ), and this can lead to the fact that the most powerful computer on Earth will be on its knees.

The problem is that you are calculating the same values ​​over and over again. Save the ExpectedValue(r,g) table and fill it in when you need to never have to calculate the same value more than once. Then you will work in O (n ² ), which is much faster.