## Friday, October 27, 2006

### streaky

There's a peculiar behavior in human psychology where something that catches your attention ends up showing up everywhere. Knuth noticed it in his discussion on randomness. We are pattern matchers: we try to make sense of the world by looking at similarity, at streaks of continuity.

So I was amused to post this and that within the same week.

## Monday, October 16, 2006

### in summation...

In an earlier post, I wondered out how to get a closed form for my car debt. The program I wrote can be actually thought of as a recurrence relation:
`   debt at the very beginning = initial debt at zero months   debt(n) = monthly interest * (debt from last month - my monthly car payment)             and where n has to be greater than 0.`

But since that's a bit wordy, I'll use some shorter variable names when I'm talking about the debt I'm incurring at month n:
`   d(n) = I * (d(n-1) - P)     for n > 0        = I * d(n-1) - I*P     for n > 0`

I didn't quite remember how to get a closed form for this formula at the time. Yesterday, though, as I was quaffing a coffee at Cape Cod, I flipped through Concrete Mathematics. There in the first few pages of the book was the technique I needed!

The core idea is to use a summation factor to make the function I'm solving for a little simpler. For the recurrence above,
`   (1/I)^n`

is a good summation factor. When I multiply my recurrence with it, I get:
`   d(n)/(I^n) = d(n-1)/(I^(n-1)) - P/(I^(n-1))     for n > 0`

The reason this is simpler is because I can consider a parallel formula:
`   S(n) = d(n) / (I^n)`

which I can use to restate the recurrence as:
`   S(0) = d(0) / (I^0) = d(0)         (since anything to the zeroth power is 1)   S(n) = S(n-1) - P/(I^(n-1))        for n > 0`

And now S(n) is, structurally, simple enough to be treated as a straight summation rather than a wacky recurrence:
`   S(n) = d(0) - sum across k from 1 to n of: P/(I^(k-1))        = d(0) - P * sum across k from 0 to (n-1) of: (1/I)^k        = d(0) - that horrendous sum`

But it turns out that that horrendous sum is actually not bad at all. If we squint our eyes at it, it's a geometric sum, and those have a very nice closed form: it's the "first term - the first excluded term in the sum, divided by one minus the term ratio". That is, if I'm doing:
`   a^0 + a^1 + a^2 + ... + a^n`

I don't have to actually add up all those terms: I can just do:
`   ((a^0) - a^(n+1)) / (1 - a)`

So by applying the transformation on that geometric sum, I can get a closed form for S(n):
`   S(n) = d(0) - P * sum across k from 0 to (n-1) of: (1/I)^k        = d(0) - P*(1 - (1/I)^n)/(1 - 1/I)`

But S(n) isn't what I was originally going after: I was going after d(n), so let me backpatch that fix in:
`   S(n) = d(n) / (I^n), so   d(n) = S(n) * I^n`

That is, my car debt at any given month is going to be:
`   d(n) = I^n * (d(0) - P*(1 - (1/I)^n)/(1 - 1/I))`

Whew! Let's try that out:
`(module car-payment-2 mzscheme ;; debt: number number number number -> number ;; Returns the amount of money owed after months pass, ;; given a particular monthly payment and apr rate. (define (debt months initial-debt monthly-payment apr)     ;; closed-form: number number number number -> number   ;; This is a closed form solution for the recurrence:   ;;   ;; d(n) = I * (d(n-1) - P)   ;;   ;; d(n) = I^n * (d(0) - P*(1 - (1/I)^n)/(1 - 1/I))   (define (closed-solution n d0 P I)     (let* ([I^n (expt I n)]            [1/I (/ 1 I)]            [1/I^n (/ 1 I^n)])       (I^n . * .            (d0 . - .                ((P . * . (1 . - . 1/I^n))                 . / .                 (1 . - . 1/I))))))     (let ([monthly-interest (+ 1 (/ apr 12))])     (closed-solution months                      initial-debt                      monthly-payment                      monthly-interest))))`

and let's look at a few values:
`> (debt 0 16300 327.93 0.0767)16300> (debt 1 16300 327.93 0.0767)16074.158147416665> (debt 2 16300 327.93 0.0767)15846.872788992236> (map (lambda (x) (debt x 16300 327.93 0.0767))      (list 0 1 2 3 4 5 6 7 8 9 10))(1630016074.15814741666515846.87278899223615618.1346983185415387.93459001529515156.26311935314214923.11088187433814688.4684130109814452.3261877008114214.6746200005313975.5040626967)> (map (lambda (x) (debt x 16300 327.93 0.0767))      (list 56 57 58 59 60))(1150.9196104211048828.2498856810436503.5177636170277176.71006207281036-152.1864853637734)`

I did a little fist-pump after I got this working. CS students are weird.

## Sunday, October 08, 2006

### the guy in the second row

I've always wondered what was up with the
guy in the second row, the person in any class that seems to hold a personal conversation with the professor. God, those people were both impressive and annoying.

God has a sense of humor. To my horror, I've found that I've become one of those people.

Sometimes I wonder if it would have been better to go with the meek and shy persona in class. Oh well. Jay Parini wrote in The Art of Teaching that a successful teacher is a stage performer, that they have no choice but to adopt a persona to become a successful teacher. I suppose that goes for students as well.