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.

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))
(16300
16074.158147416665
15846.872788992236
15618.13469831854
15387.934590015295
15156.263119353142
14923.110881874338
14688.46841301098
14452.32618770081
14214.67462000053
13975.5040626967)
> (map (lambda (x) (debt x 16300 327.93 0.0767))
      (list 56 57 58 59 60))
(1150.9196104211048
828.2498856810436
503.5177636170277
176.71006207281036
-152.1864853637734)

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

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.