/*     A procedure that computes the maximums of many random walk paths and writes
       them to a .xls file for plotting with Excel.
       Written by Jonathan Goodman for assignment 5 in the class 
	      http://www.math.nyu.edu/faculty/goodman/teaching/DerivSec10/index.html
	   
                                     */
    
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

double PathMax( double, int);   // The routine is at the bottom of this file

#define PATHS 100000     /*  The number of random paths to make  */
#define NBINS 20        /*  The number of bins for the histogram */

int main() {

   double Maxima[PATHS];
   
          // Compute the paths and the maxima, and the max max
   
   double dX = .3;       //  The step size for the random walk
   int    n  = 10000;    //  The number of steps in the random walk.
   
   double MaxMax = 0;    //  The max of all maxima
   int BinCounts[NBINS];      //  The bin counts for the histogram
   
   for ( int i = 0; i < PATHS; i++ ) {   // Compute the paths
      Maxima[i] = PathMax( dX, n);
      if ( MaxMax < Maxima[i] ) MaxMax = Maxima[i];   // and the max max
     }
   
   int bin;
   for ( bin = 0; bin < NBINS; bin++)   // Initialize the bin counts
      BinCounts[bin] = 0;
      
   double BinWidth = MaxMax / ( (double) NBINS );  
      
   for ( int i = 1; i < PATHS; i++ ) {
      bin = (int) ( Maxima[i]/BinWidth );
      BinCounts[bin]++;
     }
      
   ofstream csvFile;              // The file for output, will be csv format for Excel.
   csvFile.open ("Max.csv");      // Max.csv is the name of the output file
   
   double BinCenter;
   csvFile << " bin center , bin count " << endl;
   for ( bin = 0; bin < NBINS; bin++) {  // Print the bin centers and bin counts
      BinCenter = ( ( (double) bin ) + .5 ) * BinWidth;   // The first bin center is .5*( bin width ), etc.
      csvFile << BinCenter << ",  " << BinCounts[bin] << endl;
     }
     
   return 0;
   
 }
   
   


/*     A procedure that simulates a symmetric random walk path and reports its maximum value.
	   
	      It uses the native C random number generator rand(), which may not be that good.
	      Feel free to replace this with a better one, but remember to set the seed.                */

double PathMax(          // The return value is the maximum value on this random path.
           double dX,    // The size of a step
           int    n ) {  // The number of steps in a path.

   double Max = 0;       // The path maximum, initialized to zero
   double X   = 0;       // The location of the path after j steps
   
   int HalfRandMax = RAND_MAX / 2;  // The native C rand() produces an integer in the range [0,RAND_MAX]
                                    // The value of RAND_MAX is in the <math.h> header file.
   
   for ( int j = 0; j < n; j++ ) {
      if ( rand() > HalfRandMax )    // This is true half the time
         X += dX;                    // Step up  ...
      else                           //   ... or ...
         X -= dX;                    // Step down.
      if ( X > Max ) Max = X;        // Record the maximum
    }
   
   return Max;
}