Description
This programming exercise is meant to get you thinking about recursive
algorithms for pricing options and other financial instruments. We will use a
card-game to motivate the algorithm development. The problem statement is
as follows:
I shuffle a deck of cards (with an equal number of red and black
cards) and start dealing them face up.
After any card you can say “stop”, at which point I pay you $1 for
every red card dealt and you pay me $1 for every black card dealt.
What is your optimal strategy, and how much would you pay to play
this game?
You are going to write a C++ program, which uses recursion, that takes as
command-line input the number of cards in the deck, and comes up with the
no-arbitrage price1
for this game.
1Arbitrage occurs when you can make a profit that is in excess of the risk-free rate of
return, which is zero for this problem.
You have an arbitrage opportunity if you can create a portfolio of zero value today, but this
portfolio has a positive value in the future with a positive probability, and a negative value in
the future with zero-probability.
The “no-arbitrage principle” suggests that there are no arbitrage opportunities in any
market. This “there is no free-lunch” assumption is the corner-stone of classical finance
theory (cf. section 3.2, [?]).
1
Hints
1. The no-arbitrage price is at least zero. Because, you can wait till all cards
are dealt (and there is the same number of red and black cards dealt;
and you owe nothing).
2. You should ask for another card only if the expected value of continuing to
play is greater than the amount of money already won by you. Otherwise,
you should say “stop.”
3. If value(#red cards left, #black cards left) is a function that computes the
value of the game to you at any point, then
value(#Red cards left, #Black cards left)) =
max {(Prob of Red Card drawn) × value(#Red cards left-1, #Black cards left))+
(Prob of Black Card drawn) × value(#Red cards left, #Black cards left – 1)),
(#Black cards left – #Red cards left) (1)
(??Why??)
4. Think of a recursive implementation (after presenting an appropriate justification) for equation 1 shown above.
(a) A naive implementation of the recursion will run into run-time problems (cf. figure 1) when the size of the deck exceeds 35.
(b) Look up the method of memoization to come up with a faster implementation of the recursion, which can handle large card deck size
with ease (cf. figure 2). Or, you could just pay attention when I
cover this in class ^¨ .
Here is what I want from you for this programming assignment
1. C++ code with appropriate Class definitions that takes the size of the
deck as input and returns the arbitrage-free price for playing the game.
Your implementation should be able to handle a deck with 52 cards, at
least.
References
2
Figure 1: Sample output. Notice the growth in running-time as the #cards in
the deck is increased. We have think of something to overcome this issue. We
want to be able to handle decks of size 52 or higher! See sample output in figure
2.
3
Figure 2: Sample output of an implementation that can handle cases where the
#cards in the deck is large. See sample output in figure 1 for a comparison of
run-times.
4
