Mathematics of a Perfect Hash

This is in response to a problem known as the "Kember Identity". I wanted to know if this search was in vane, or had some chance of success. The third requirement of a Hash is that "It is computationally infeasible to find messages m₁ and m₂ with h(m₁) = h(m₂) (in this case, the function h is said to be strongly collision-free)" (Trappe p219). Given that statement it is reasonable to state that the bits of the hash should be randomly flipped.

The idea of the Kember Identity is simple, find a hash of a message (in this case MD5) such that: h(m) = m. In order for this to occur the bits of at least one 128-bit message need to hash into the same 128 bit digest. Assuming a hash that has the property of treating all bit combinations as equal even its own, there is a 1 in 2¹²⁸ chance that any single value will achieve this. This can be restated as there is a 2¹²⁸-1 in 2¹²⁸ chance that it will be anything else. The question is what are the odds that all 2¹²⁸ will be anything else, the answer is:



Using my favorite package to ask big math questions on (PARI), I came up with an answer of approximately 37%. That means there is a 37% chance that in a perfect hash there will be no combination of a 128-bit message that will produce the same output. To put it in the reverse which I am sure my friend who is searching for the "Kember Identity" is interested in, that means that there is a 63% percent chance that there is at least one 128-bit message whose digest is the same.

Kember came out here much better then I predicted. I should have remembered the lessons of the Birthday Paradox. Needless to say if MD5 performs near the assumptions above there is a better then 50/50 chance that such a hash exists. I wish Kember the best of luck in his search.

UPDATE: Since 2¹²⁸ is a very large number lets see what happens when the above equation goes to infinity:



Which gives an answer near the long and more correct way to calculate this.

Overpayments on Loans

Someone came up to me today and asked about what are known as Bi-weekly loans. The statement he made at first was slightly counter intuitive, "You can make half your monthly payment and pay off your loan in six to eight years earlier." I was doubtful, and the math did not yield the result, if anything more compounding cycles means you would pay more over 30 years not less.

The "trick" or lie (if your the bank) is that with the Bi-weekly schedule you actually make what is equivalent to an extra month payment every year. My contention was that if you overpaid the mortgage by the same amount each month that would sum up to what you where effectively doing with a Bi-weekly schedule you would wind up in the same position or near the same position, so lets take a look at that.

Resolving our relationship X from the previous article for nt yields:



So if you overpay OP by X/12 each schedule you will find that you will pay the loan off by about the same amount of time. Example r = 4%, t = 12, X = 1432.25, P = 300,000. Note that a payment of 1432.25 is what it takes pay of the loan in 30 years. Applying this the equation above we find that overpaying by the specified amount would yield 310.78 terms or you would be able to pay it off in 25 years and 11 months, the last month you would make a reduced payment of $1211.

So if you don't want to refinance your loan, just make the overpayment and make sure to write on the stub that you want the additional amount to be applied to the principal.

Here a geometric series there a geometric series

Over the past two weeks I have been running into geometric series everywhere. Geometric series are simple little equations that have the form of:



There is wiki that goes into the basics of geometric sums and their basic identies on Wikipedia: http://en.wikipedia.org/wiki/Geometric_series. For now I only present to you one of the places I have run into this little bad boy, and that is in the calculation of amortization. Every time I go through a application that does this I wondered where the math came from, I finally decided to work it out for my self.

Lets start with the knowns, r is the yearly APR, t is the number of times the APR is compounded in a year, n is the number of years, P is the principle on the loan, and D is your down payment. The only variable we are looking for X is your monthly payments. At the end of the loan term or n*t payments we would like there to be no balance in the account.

First the amount that in the loan has to start with:



Each subsequent payment takes interest from the previous period, and deducts your payment:





Expanding the recursive relationship manually reveals a equation that can have Horner's Rule applied to reduce it to a more manageable form:



Transposing by Horner's Rule and collapsing the subsequent series into a Geometric Series:



Apply the identity from the Wikipedia page above:



Recalling that at the end of the term we desire no net balance, solving for X and simplifying:





Now I have the magic amortization formula in my back pocket in case I ever need it again. You can also quickly calculate your total payments Xnt or the amount of interest you paid Xnt - (P - D). The two other areas I have had the Geometric Series show up was calculating the probability of winning at a game of dice, and a 401k what if Excel sheet I made. The Dice game is really interesting because it deals with an unbounded Geometric Series.

UPDATE: A simplification of the formula above is possible:



If you know how much you can pay each month X and are looking for how much of a mortgage you can afford you can resolve the equation above for P-D



Also note that there is a linear relationship between the amount you can pay and the amount of a mortgage you can afford.



UPDATE: Homer's Rule replaced with Horner's Rule

Why Traditional 401k wins, assuming same tax rate

One of my friends asked me to explain why the Traditional 401k wins over the Roth 401k in more detail assuming the tax rates are the same as when they retire. Lets assume an individual makes $50,000 today, this means he is taxed at an average tax rate of 11.9% (Federal Income only) but is in the 25% tax bracket. Lets say the same individual puts away $2500 dollars.

This means that his average tax rate dropped to 11.21%, also his take away income only dropped $1875. Now lets say we assume he retires as the financial experts say with 80% of todays income, or 40,000. When he re walks the system his tax rate has dropped even again to 9.45% of his income coming out of the 401k, and he has even dropped to the 15% bracket.

In the case of the Roth 401k you are always at a tax rate of 11.9%. This means when you assume that taxes will go up in the future (comparing the Roth to the Traditional) you must also assume the tax rates will go up enough in the future to cancel out this effect. Since I don't see the marginal tax system in the country going any where I am going to assume that odds are you are going to find that it will probably stay the same or even get better unless you are in the top 2%.

Source for Tax Calculations: http://www.dinkytown.net/java/TaxMargin.html

Traditional 401k vs Roth 401k

There are a lot of factors to consider when choosing whether or not to contribute your money twords a Traditional or Roth 401k if your company offers both. Here are some things to consider when comparing the two:

• What is the income you are making now vs the amount that you want when you retire?
• Does your company match?
• Do you think taxes will be higher or lower for you when you retire?
• Will you max out the 401k?
• When do you want to retire?

The key differance between a Traditional 401k and a Roth 401k is that in a Traditional you do not pay taxes now, rather you pay taxes when you take the money out. On the other hand the Roth 401k is different in the sense that you pay taxes now, but when you take the money out you don't pay taxes.

If you assume no company match and the tax rate today is going to be the same as when you retire, the two are generally considered a wash. This is actually untrue, the reason is when you defer your Traditional 401k contrabitions they are deferred at the highest taxable bracket that you are currently in. When you take out the money after you retire you re-walk the marginal tax brackets, this means that the money is actually taxed at a lower taxable rate when you take it out. Therefore dollar for dollar the Traditional 401k makes more sense assuming equivalent tax rates.

When talking about where tax rates are now and where they will be when you retire this depends on you as a individual as much as it does the bureaucrats in DC. If you are a lowly slug in the food chain right now, and you retire as a CEO it is clear that you are on a lower tax bracket now as the lowly slug then you will ever be in your entire life, so in this case the Roth makes sense. It also depends on what you think the cronies on capital hill will do with the laws between now and when you retire. Many assume that taxes will be higher then they are now, and therefore argue that the Roth 401k is advantageous. I argue that it is difficult to gauge either way, if you take historical trends into account its really hard to pin down where taxes will go.

If your company offers a match generally the match is better in Traditional because the match is made as a Traditional 401k, so you have to pay taxes on the match when you take it out. Since the amount of match that you get when you contribute to a Roth is effectively lower you are better positioned when you apply your match to a Traditional 401k.

If you can max out the 16,500 contribution limit, then it always makes sense to go Roth, because you can end up contributing more then with a traditional 401k. The last thing you must consider is when you are planning to retire. Current Traditional 401k law forces you to begin taking out minimum 401k distrabutions at the age of 70 1/2, if you plan on retiring much later say 80, you might want to consider the Roth 401k.

There is nothing to stop you from contributing to both the Traditional and Roth 401k's. As always you must pick an investment strategy that not only you are conferable with, but makes sense for you as well.

UPDATE: In the case of the Roth only a Roth IRA prevents you from having to take the distribution at 70 1/2. So if you want to avoid it you have roll it over to a IRA.

UPDATE 2: The forced distribution age was changed form 59 1/2 to 70 1/2.

A "Small" loss in GDP Growth.

I was watching the Bill Maher show, and some colossal bag of ignorance stated that, "We can stand to sacrifice a small amount of GDP growth" for the sake of social programs. He admitted that conservatives are correct that such social programs do stifle GDP growth, so at least the conservatives are winning on that front.

What is amazing to me is this man claims to understand the economy, if I went up to him and asked him, "should start saving for retirement now or ten years from now?" His response to my question would be to start saving now. So I am sure that he understands the concept of compound interest, but why can't he understand that it affects the country in the same way. Lets look at a table of how different GDP growth rates would affect a country year to year. We start with country having a base GDP index of 100.

Years	3%	5%	8%
0	100.00	100.00	100.00
1	103.00	105.00	108.00
5	115.93	127.63	146.93
10	134.39	162.89	215.89
30	242.73	432.19	1006.27
50	438.39	1146.74	4690.16
100	1921.86	13150.13	219976.13

As you can see from the table above, even a small delta in GDP growth in a human life span is absolutely staggering. What is even more interesting is if you assume that each one of these is a country. The country that has the Annual GDP growth of 8% per year might have little to no social programs, however, its economy is 17 times larger then the economy with 5% growth, and 114 times larger then the country with 3% growth at the end of 100 years. This means that even the "poor" in the country with 8% GDP growth are most likely better off then the people receiving services in the countries that have 5% and 3% GDP growth. We see exactly this in America, although our assistance to the poor is low from a GDP standpoint, we don't have to assist that much because our per capita GDP is so high. If you reduce that per capita GDP it means you need more social programs, its a self destructive cycle. We also see this when we look at the history of the USA and Mexcio, in the 1850's the two countries economis where about equal, now the USA economy is much stronger the Mexico's, the GDP growth of the USA was simply much larger then Mexico's.

The key here is the power of compounding, the fact that so many people can ignore the effects of compounding in the long term is why we don't have more people saving at a young age. So when you are looking at the effects of compounding remeber it is always a powerful force wether it is your retirment account, or the strength of the country that you live in.