COS 126

A Pseudo-Random Walk on Wall Street
Programming Assignment 4

Due: Wednesday, 11:59pm


The goal of this assignment is to help you understand how TOY and the TOY simulator work, and to illustrate that relatively simple computational models can handle useful and nontrivial calculations. You will write a TOY program to estimate the expected value of a certain stock option.

Overview. Consider a stock option for a fictitious company COS126 Corporation. The strike price is $55 and the expiration date is in 30 days. This means that you have the option to purchase one share of COS126 Corp for $55 in exactly 30 days. If the price of COS126 Corp exceeds $55 in exactly 30 days, the option is in the money since you could exercise your option and purchase 1 share for $55, then immediately sell it for a profit. You are not required to exercise your option, so if the stock price does not exceed $55, you will just throw it away. Note that you are only permitted to exercise the option on the expiration date. In finance lingo, this option is called a European call.

The current price of COS126 Corp. is $50/share. Suppose the price of the stock could be accurately modeled by the following random process. Each day, with equal likelihood and independently, the stock price either increases by $1 or decreases by $1. Your assignment is to write a TOY program to compute the expected value of the option after 30 days. If the stock price is $55 or less after 30 days, then the option is worthless. Otherwise, its value is the difference between the ending price and $55.

Some perspective. This famous and well-studied process is called a random walk. Many natural phenomenon (including the gamblers ruin problem from Lecture 2) have been modeled using this same process or variants. The random walk only allows discrete movements ($1 at a time). A continuous version of this process called Brownian motion is used in the Black-Scholes model to price options. Brownian motion is also widely used to model the dispersion of ink flowing in water, and the behavior of atomic particles predicted by quantum physics.

The basic simulation. To estimate how valuable your option is after 30 days, consider the following simulation:

  • repeat 30 times
  • generate a pseudo-random bit
  • increase the stock price by 1 if the bit is 1; otherwise decrease it by 1
  • if the final price is $55 or less, output 0; otherwise output the difference between the final price and $55.
  • To get a good statistical estimate of the expected value of your option, perform this simulation 255 times. Count up the total value V of the option over the 255 simulations, and print out this running total after each of the 255 simulations. Then, compute V/255 with a calculator: this estimates the expected value of the option.

    TOY simulator input upgrade. To help you write and debug your TOY program, we have enhanced the input format. Instead of just listing TOY instructions, the enhanced C TOY simulator makes you write the memory address of each instruction, and also allows you to include comments in your TOY code. Alternatively, you can use the Java TOY simulator. As an example, consider the following TOY program which simulates the linear feedback shift register (LFBSR) from Lecture I1.

    
    
    
    
    00: 0684                                 // contents of LFBSR stored here
    
    10: B61E   R6 <- 30                      //  do { R6 = 30
    11: 81F0     jump and link to F0         //    R3 <- new bit (using function) 
    12: 4300     print R3                    //    print R3
    13: 7611     R6--; if (R6 > 0) goto 11   //    R6--
                                             //  } while (R6 != 0)
    14: 0000   halt                          
    
    F0: 9200   R2 <- mem[0]                  // simulate one step of a LFBSR
    F1: 9300   R3 <- mem[0]                  
    F2: B001   R0 <- 1                       
    F3: E203   R2 <- R2 >> 3                 // put 3rd bit of LFBSR in R2
    F4: D220   R2 <- R2 & 1                  
    F5: E30A   R3 <- R3 >> 10                // put 10th bit of LFBSR in R3
    F6: D330   R3 <- R3 & 1                  
    F7: C323   R3 <- R2 ^ R3                 // new bit (XOR of 3rd and 10th bits)
    F8: 9200   R2 <- mem[0]                  // update LFBSR
    F9: F201   R2 <- R2 << 1                 
    FA: 1223   R2 <- R2 + R3                 
    FB: A200   mem[0] <- R2                  
    FC: B000   R0 <- 0                       // return using indexed addressing
    FD: 5801   pc <- R0 + R1                 // jump to addr in R1            
    

    Generating pseudo-random bits. It is impossible to generate truly random bits in the TOY programming language. Instead, you will generate pseudo-random bits by simulating a LFBSR on your TOY machine. In the TOY program above, the function starting at memory location F0 performs one iteration of the LFBSR. The LFBSR contents are stored in memory location 00. The whole routine is packaged up as a function. As in Lecture I1, we use 0684 as the starting fill pattern. (There is no special significance to this number, but use it for consistency.) The "main" program (starting at memory location 10) calls this function using opcode 8 (jump and link) 30 times, printing out the pseudo-random bit after each call. Each function call to the LFBSR produces a new pseudo-random bit in register R3. Use this bit to determine whether the stock price goes up or down by $1.

    Using the TOY simulators. The C TOY simulator reads the program from standard input and prints to standard output, so you can execute with "a.out < option.toy". The Java TOY simulator reads the program from an html file, and has a graphical user interface. You may use either simulator to develop and debug your program, but your submission should be a text file named option.toy that works with the C simulator supplied.

    What to submit. Submit the files readme and option.toy. Your TOY program should be amply commented. Your readme file should contain a description of your code and a table of what each register is used for. Also, calculate an estimate of the value of 1 option in dollars and cents, i.e., V / 255.



    This assignment was developed by Robert Sedgewick and Kevin Wayne
    Copyright © 2000 Robert Sedgewick