| COS 126 A Pseudo-Random Walk on Wall Street |
Programming Assignment 5a Due: Wednesday, 11:59pm |
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 minor 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 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 TOY simulator makes you write the memory address of each instruction, and also allows you to include comments in your TOY code. Here's the source code for the TOY program that is discussed in the next paragraph.
Your TOY program will use jump or goto statements that hardwire in the memory location (like 11 in instruction 7611 below) of the next instruction to be executed. This means that if you insert a new instruction, you may have to modify each jump statement in order to jump to the right place. You will greatly appreciate the ability to include line numbers in your code. You should also appreciate the advantages of a structured programming language, like C, that allows while and for loops, instead of relying solely on goto statements.
00: 0684 // contents of LFBSR stored here 10: B61E R6 <- 30 // number of bits to generate 11: 81F0 jump and link to F0 // R3 <- pseudo-random bit (using function) 12: 4300 print R3 // output R3 to screen 13: 7611 R6--; if (R6 > 0) goto 11 // decrement R6 and continue loop 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 F4: D220 R2 <- R2 & 1 // 3rd bit of LFBSR F5: E30A R3 <- R3 >> 10 F6: D330 R3 < R3 & 1 // 10th bit of LFBSR F7: C323 R3 <- R2 ^ R3 // new pseudo-random bit (XOR of 3rd and 10th bits) F8: 9200 R2 <- mem[0] F9: F201 R2 <- R2 << 1 // update LFBSR FA: 1223 R2 <- R2 + R3 // update LFBSR FB: A200 mem[0] <- R2 // update LFBSR FC: B000 R0 <- 0 FD: 5801 jump to addr in R1 // uses indexed addressing mode
TOY instruction set upgrade. Before you will be able to write the TOY program, you will perform one "upgrade" to your TOY simulator. In this assignment, you will need to compare the values of two registers (e.g., to compare the final stock price with the strike price). This is a bit cumbersome in the current TOY machine, since there is no support for negative numbers (negative numbers would overflow and become positive numbers). Replace opcode 3 (don't worry, you won't need to multiply in this assignment) with a "compare and increment" instruction that takes 3 registers, and increments the first register by one if the contents of the second register is greater than the contents of the third. An example is given below.
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 linear feedback shift register (LFBSR) on your TOY machine. The LFBSR is described in Lecture 1. 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.15: 3406 if (R0 > R6) R4++
Extra credit: Modify your TOY program so that it does
not need to use the new opcode 3 instruction.