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 estimate the probability that your option will be in the money in 30 days, i.e., after 30 days the price will be $56 or more.

Some perspective. This famous and well-studied process is called a random walk. Many natural phenomenon (including the gambler's 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 likely your option is to be "in the money" after 30 days, consider the following simulation:

To get a good statistical estimate of the probability that your option is in the money, perform this simulation 255 times. Count up the number of times T that you output yes. Then, T/255 estimates the probability that your option will be in the money.

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 1.

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   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. It is almost identical to the one in Lecture 5.8, except that the LFBSR contents are stored in memory location 0 instead of R1. Also it is packaged up as a function, similar to Lecture 5.9. As in TOY program 4, 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 pseduo-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.