The Value of an AnnuityThe Future Value of MoneyA Geometric SumReturn of the Annuity ProblemInfinite SumsSums of PowersEvaluating the SumWhere Do the Formulas Come From?Approximating FunctionsTaylor's TheoremRule of 72Upper and Lower BoundsApproximating 1 + xA Large-x Approximation� �6.042/18.062J Mathematics for Computer Science March 10, 2005 Srini Devadas and Eric Lehman Lecture Notes Sums and Approximations When you analyze the running time of an algorithm, the probability some procedure succeeds, or the behavior of a load-balancing or communications scheme, you’ll rarely get a simple answer. The world is not so kind. More likely, you’ll end up with a complicated sum: n� 1 k +√kk=1 Or a nasty product: � �� �� �� �1 2 3 n 1 + 1 + 1 + 1 + 2 2 2 2n n n··· nOr you might get an answer that is just tad too complicated to grasp intuitively: 72/n n 1 + 100 And these examples are relatively benign! So the ability to cope with such messy mathematical expressions is an important skill in computer science— and in many other areas of science and engineering. This might not seem glorious, but people who can cut monstrous expressions down to size in moments can seem pretty amazing to the uninitiated. This week, we’ll equip you with the most useful tricks of the trade. 1 The Value of an Annuity Would you prefer a million dollars today or $20,000 a year for the next fifty years? This is a question about the value of an annuity, a financial instrument that pays out a fixed amount of money at the beginning of every year for some specified number of years. In particular, an n-year, $m-payment annuity pays m dollars at the start of each year for n years. In some cases, n is finite, but not always. Examples include lottery payouts, student loans, and home mortgages. There are even Wall Street people who specialize in trading annuities. For many reasons, $20,000 a year for 50 years is worth much less than a million dollars right now. For example, consider the last $20,000 installment. If you had that $20,000 right now, then you could start earning interest, invest the money in the stock market,2 Sums and Approximations or just buy something fun. However, if you don’t get the $20,000 for another 50 years, then someone else is earning all the interest or investment profit. Furthermore, prices are likely to gradually rise over the next 50 years, so you when you finally get the money, you won’t be able to buy as much. Finally, people only live so long; if you were 60 years old, a payout 50 years in the future would be worth next to nothing! But what if your choice were between $40,000 a year for 50 years and a million dollars today? Now which is better? What is an annuity is actually worth? 1.1 The Future Value of Money In order to address such questions, we have to make an assumption about the future value of money. Let’s put most of the complications aside and think about this from a simple-minded perspective. The average rate of inflation in the United States from 1980 to 2004 was about p = 3.5% per year. This means that the price of a selection of basic goods increases by about 3.5% each year. If this trend continues, then goods costing $100 today will cost: $100(1 + p) = $103.50 in 1 year $100(1 + p)2 = $107.12 in 2 year . . . $100(1 + p)k in k years Looked at another way, k years from now, $100 will have the buying power of just 100/(1+ p)k dollars today. Now we can work out the value of an annuity that pays m dollars at the start of each year for the next n years: payments current value $m today m $m in 1 year m 1 + p $m in 2 years m (1 + p)2 ··· ··· $m in n − 1 years m (1 + p)n−1 n−1� mTotal current value: V = (1 + p)k k=0�Sums and Approximations 3 So to compute the value of the annuity, we need only evaluate this sum. We could plug in values for m, n, and p, compute each term explicitly, and then add them all up. However, this particular sum has an equivalent “closed form” that makes the job easier. In general, a closed form is a mathematical expression that can be evaluated with a fixed number of basic operations (addition, multiplication, exponentiation, etc.) In contrast, evaluating the sum above requires a number of operations proportional to n. 1.2 A Geometric Sum Our goal is to find a closed form equivalent to the summation: n−1� m m m m V = = m + + + . . . + (1 + p)k 1 + p (1 + p)2 (1 + p)k−1 k=0 This is a geometric sum, which means that consecutive terms all have the same ratio. In particular, the second term is 1/(1 + p) times the first, the third is 1/(1 + p) times the second, and so forth. And we’ve already encountered a theorem about geometric sums: Theorem 1. For all n ≥ 1 and all z = 1: � nn−1k 1 − zz = 1 − z k=0 This theorem can be proved by induction, but that proof gives no hint how the for-mula might be found in the first place. Here is a more insightful derivation based on the perturbation method. First, we let S equal the value of the sum and then “perturb” it by multiplying by z. S = 1 + z + z2 + . . . + zn−1 zS = z + z2 + . . . + zn−1 + zn The difference between the original sum and the perturbed sum is not so great, because there is massive cancellation on the right side: S − zS = 1 − z n Now solving for S gives the expression in Theorem 1: n1 − zS = 1 − z You can derive a passable number of summation formulas by mimicking the approach used above. We’ll look at some other methods for evaluting sums shortly.� �� � � �4 Sums and Approximations 1.3 Return of the Annuity Problem Now we can solve the annuity pricing problem! The value of an annuity that pays m dollars at the start of each year for n years is: n−1� m V = (1 + k)p k=0 n−1� 1k = m z (where z = )1 + pk=0 n1 − z= m · 1 − z n 11 − 1+p = m � �· 11 − 1+p We apply Theorem 1 on the second line, and undo the the earlier substitution z = 1/(1+p) on the last line. The last expression is a closed form; it can be evaluated with a fixed number of ba-sic operations. For example, what is the real value of a winning lottery ticket that pays $40, 000 per year for 50 years? Plugging in m = $40, 000, n = 50, and p = 0.035 gives V ≈ $971, 063. You’d be better off taking the million dollars today! 1.4 …
View Full Document
Unlocking...