Generalized Abstract Nonsense

ABOUT ME

psyche (sī'kē) n. 1. That which is responsible for one's thoughts and feelings. 2. The seat of the faculty of reason.

syllogism (sĭl'ō-jĭz'əm) n. 1. Reasoning from the general to the specific. 2. A subtle or specious piece of reasoning.

psyllogism (sī'lō-jĭz'əm) person: A twenty-something college graduate, software engineer, and geek extraordinaire. I am recently married and trying to manage life, friends, family, a job, and an (un)healthy gaming hobby.

Articles * Blog * Profile * Calendar * Photos

Interfaces

1252948319|%c

I'd be far more willing to use more ubiquitous interfaces in Java if I could do something akin to the following:

public interface SomeInterface {
    public void foo();
 
    public void bar();
}

public class SomeInterfaceImpl implements SomeInterface {
    public void foo() {
        System.out.println("Hello, world from SomeInterfaceImpl!");
    }
 
    public void bar() {
        System.out.println("Hello, world from SomeInterfaceImpl!");
    }
}

public class SomeClass implements SomeInterface {
 
    // Delegate all calls to foo() here.
    private SomeInterface someInterfaceInstance implements SomeInterface;
 
    public SomeClass(SomeInterface someInterfaceInstance) {
        this.someInterfaceInstance = someInterfaceInstance;
    }
 
    @Override
    public void bar() {
        System.out.println("Hello, world from SomeClass!");
    }
 
    public static void main(String... args) {
        SomeInterface someInterfaceImpl = new SomeInterfaceImpl();
        SomeClass someClassInstance = new SomeClass(someInterfaceImpl);
 
        someClassInstance.foo();
        someClassInstance.bar();
    }
}

> java SomeClass
> Hello, world from SomeInterfaceImpl!
> Hello, world from SomeClass!

This keeps you from having to type out this method on SomeClass:

@Override
public void foo() {
    this.someInterfaceInstance.foo();
}

Which is hella annoying. And yeah, you could get your IDE to do that for you, but then it adds clutter to your source code when you or somebody new comes to look at it later. Besides, the less typing/clicking there is, the more productive I can be! Plus, this promotes composition over inheritance, a lofty goal in software engineering. Win win, don't you think?

Show Comments

Method Overloading

1250876532|%c

This is annoying. Given the following Java code snippet:

public class Overloading {
 
    public void foo(Object object) {
        System.out.println("I'm an object!");
    }
 
    public void foo(String string) {
        System.out.println("I'm a string!");
    }
 
    public void foo(List<?> list) {
        System.out.println("I'm a list!");
    }
 
    public static void main(String... args) {
        Overloading overlord = new Overloading();
 
        Object str = "Hello, world!";
        overlord.foo(str);
 
        Object lst = new ArrayList();
        overlord.foo(lst);
    }
}

When I run it, it gives me the following output:

> java Overloading
I'm an object!
I'm an object!

That's not what I want Method Overloading to do :-(

Show Comments

Alarm Clock

1244815288|%c

BEEP BEEP BEEP BEEP BEEP BEEP BEEP BEEP

My alarm clock starts going off at 5:33 AM, as it does almost every weekday morning. I hit the snooze button.

BEEP BEEP BEEP BEEP BEEP BEEP BEEP BEEP

Nine minutes later, at 5:42 AM, my alarm clock wakes me up again. I've always wondered why nine minutes seems to be the standard with many models of alarm clocks?

BEEP BEEP BEEP BEEP BEEP BEEP BEEP BEEP

It's 5:51 AM. "Hmm, that's interesting," my tired mind exclaims. "The digits for each of the 'minute' part of those times adds up to six. 3+3=6, 4+2=6, 5+1=6…Now why would that be?"

I roll over in bed, waking up to this thought process: "Well, is that true for all two digit numbers? Let's take a number made up of two digits, $a$ and $b$ . Then that number is equal to $10a + b$ . Then we add 9 to it, so we get $10a + b + 9$ . Well, 9 is just 10 - 1, so we have $10a + b + 10 - 1 = 10(a+1) + (b-1)$ , which, if $a < 9$ and $b > 0$ , is another two digit number, with digits $a+1$ and $b-1$ . And look, $(a-1)+(b+1) = a + b$ , so the sum of the digits is the same! Eureka! I have found it! That's why the digits for the minute parts all add up to six!

BEEP BEEP BEEP BEEP BEEP BEEP BEEP BEEP

It's now 6:00 AM. It's time for me to get up and get ready for work for the day. Besides, the interesting pattern is over: $0 + 0 \neq 6$ .

Show Comments

The Lottery is a Tax on People Who Are Bad at Math

1229201709|%c

The Math Tax

Tuesday

It is a common adage that the lottery is a tax on people who are bad at math. Well, I don't consider myself bad at math, but I've still been known to play the lottery on occasion

In fact just the other day my sister saw a lottery ticket on my nightstand and exclaimed, "You play the lottery?!" she asked incredulously. I replied, "When I notice that it's over about $100 million and I have some money in my pocket, sure, I'll buy a ticket. It's fun."

But being mathematically inclined, that got me thinking: is playing the lottery worth it even when it's at $100 million? A very quick analysis shows that even then it is not. First off, the advertised value of $100 million is based on how much the state thinks it can pay you over 20 years of payments. There is also a "lump sum" pay out with most lotteries where you just get all of your money all at once; it's just rather less than the advertised value. Basically the advertised value is just the lump sum + 20 years' interest (at a rather low interest rate, nonetheless). Secondly, the odds of winning the jackpot are less than 1 in 175 million. The expected value then of even a $100 million jackpot is far less than $1, which is the cost of a ticket. Since the "lump sum" value is even smaller than $100 million, the expected value is even less. Finally, taxes take away a significant chunk of your winnings, too. Things are looking bleak indeed!

Heads or Tails?

Wednesday

And an even deeper analysis shows that it's even worse than that. That's because, two or more tickets can have the same number, and if all of them win, they split the jackpot evenly. This makes your expected value even less!! How much less? That's what I was about to discover.

On the Metro ride home the next day, I started contemplating what the "true" expected value of the jackpot was, taking into account the fact that the jackpot might be split. To do so, I started simply. Let's say I was going to flip a coin and have you guess heads or tails. If you're right, I'll give you $1. If you're wrong, you get nothing. Okay, then the expected value is an easy calculation: you have a 50% chance of being right, so on average you will win $0.50. That means if I charge you anything less than $0.50 to play, it would be considered "rational" to go ahead and play: your expected reward is higher than your cost.

But let's say there are two of you. Both of you independently guess "heads" or "tails". I then flip one coin. If either one of you is right and the other wrong, the one who is right gets a dollar. If neither of you are right, both of you get nothing. However, if both of you are right, you split the dollar and both of you get $0.50. What's your expected value?

To start with, I scribbled out a table on a discarded newspaper that was left beside my metro seat. It looked something like this:

Player 1's guess	Player 2's guess	Coin flip outcome	Player 1's reward	Player 2's reward
H	H	H	$0.50	$0.50
H	H	T	$0	$0
H	T	H	$1	$0
H	T	T	$0	$1
T	H	H	$0	$1
T	H	T	$1	$0
T	T	H	$0	$0
T	T	T	$0.50	$0.50

And Player 1's average reward is $0.375, which is less than the $0.50 they would have gotten if they were the only player. Now, it is only "rational' to play if the cost is less than $0.375!

How do I generalize this to a lottery, where there are far more than 2 players and 2 outcomes? That was my next task. To do so, on another page in this discarded newspaper (and let me tell you, it's hard to find mostly empty places in newspapers to draw these things), I started to flesh out a decision tree for the possibilities in a lottery. Again, I started with two players but with any number of equally possible outcomes.

In the first step, Player 1 chooses their desired outcome (i.e., their lotto numbers) out of $N$ possible outcomes. Then Player 2 effectively has two choices: they could choose the exact same outcome as Player 1 (which has a $1/N$ chance), or they choose any of the other possible outcomes (which has a $N-1 \over N$ chance). Then we run the lottery, and from each of those choices comes two possibilities: The outcome is the one that Player 1 chose (which has a $1/N$ chance), or the outcome is another outcome (which has a $N-1 \over N$ chance). Let $R$ be the value of the jackpot reward. Then the expected value is calculated to be:

(1)

${R \over 2} \cdot \left({1 \over N} \cdot {1 \over N}\right) + 0 \cdot \left({1 \over N} \cdot {N-1 \over N}\right) + R \cdot \left({N-1 \over N} \cdot {1 \over N}\right) + 0 \cdot \left({N-1 \over N} \cdot {N-1 \over N}\right)$

Well that's gobblygook, isn't it? Even "simplified", it looks like:

(2)

$\left({2N - 1 \over 2N^2}\right) R$

Which gives us the right answer (plug in "2" for $N$ and "$1" for $R$ ), but doesn't give us any insight into what is going on. To get some more intuition, I sketched out the decision tree for three and even four players. And then the answer came to me from back in Combinatorics class my senior year of college. This probably will be very hard to explain, so bear with me here.

(Click to enlarge)

In the 3 player decision tree, we see that one of the terms is repeated twice (colored purple). In the 4 player tree, we see that two of the terms (one in purple, the other in white) are each repeated three times. Is there any rhyme or reason to these repetitions? I say there is.

What's happening each time a term is repeated? Look closely! Each time a term is repeated, the same number of other players has chosen an outcome other than Player 1's outcome. It doesn't matter which player(s) have chosen a different outcome, just that the same number of them have.

In the 4 player decision tree, the term $(N-1)^2 \over N^4$ represents the proportion of times that 2 other players have chosen something other than Player 1's outcome, and the term $(N-1)^3 \over N^4$ represents the proportion of times that 3 other players have chosen something other than Player 1's outcome. We just have to count the number of times that happens. If only there were a way to mathematically compute the number of possible ways to choose a number of people from a total set of people…

Oh wait, there is! This was where I used my memory of Combinatorics class.

Okay, now we have an intuition into how to generalize the expected value calculation. Let $K$ be the total number of players playing the lottery. When $j$ other players choose an outcome other than Player 1's outcome, then Player 1's expected value is given by:

(3)

${K-1 \choose j}\left({(N-1)^j \over N^K}\right)\left({R \over K - j}\right)$

Thus, Player 1's total expected value given a jackpot reward of $R$ , which is computed by adding together all of the possible expected values for each $j$ , is:

(4)

$E(R) = \sum_{j=0}^{K-1}\left[{K-1 \choose j}\left({(N-1)^j \over N^K}\right)\left({R \over K - j}\right)\right]$

And that was as far as I got on my hour-long ride home from work that night.

Pascal's Triangle

Thursday

The next day, I was mulling it over in my head. I wanted to see some results now. "I know! I can program this!" I thought, and I did, very quickly. But problems quickly arose when I tried computing with real-world lottery numbers. Remember when I said that the odds of winning the jackpot are less than 1 in 175 million? That means that the $N$ above is bigger than 175 million. When I start to have the number of players $K$ playing the lottery get any higher than 20 or 30, the calculations quickly become way to big for the computer to handle. Even when I changed to handling the number using Java's BigDecimal class, the time it took to compute the combinations and exponents in that formula would take hours even for small number of players.

I tried to simplify the formula naively, just canceling out fractions and pulling out terms like you learn in middle school algebra, but to no avail. I had to be more clever. I knew there had to be a better solution.

Then on the Metro ride home that second evening, I remembered Pascal's triangle.

Why look, in the Wikipedia article there, it's talking about the binomial coefficient, which we used to compute the number of combinations of player's who chose differently than Player 1! How convenient. What Pascal's triangle reminded me of (after a small bit of scribbling) was that the $M$ th row of the triangle gave me the coefficients of $(x+1)^M$ . Or, more tersely, I was able to remember this particular mathematical identity:

(5)

$\sum_{i=0}^{M}{M \choose i}x^i = (x+1)^M$

Can we make our formula from step (4) above look anything like that? At first I couldn't. I tried setting $M = K-1$ and $x=N-1$ , but that pesky $K - j$ in the denominator of the last term got in my way. For fun, I tried just removing that $K-j$ to see what would happen. I came up with $E(R)=R/N$ ! Which is much simpler, but, obviously, wrong. Why? Because I wasn't dividing the jackpot among all of the winners! So alas, that evening, I was stuck. I resolved to sleep on it.

Eureka

Friday

The next morning, I had an epiphany. I knew what to do with that pesky $(K-j)$ in the denominator! Here's how: By definition:

(6)

${{K-1} \choose j} = {(K-1)! \over {j! (K-1-j)!}}$

so it follows that:

(7)

${{K-1} \choose j}{1 \over (K-j)} = {(K-1)! \over {j! (K-1-j)!}}{1 \over (K-j)} = {(K-1)! \over {j! (K-j)!}}$

Now just multiply the top and bottom by $K$ and we get

(8)

${K \over K}\cdot{(K-1)! \over {j! (K-j)!}} = {1 \over K}\cdot{K(K-1)! \over {j! (K-j)!}}={1 \over K}\cdot{K! \over j! (K-j)!} = {1 \over K}\cdot{K \choose j}$

and $K$ is a constant, so we can just factor it out of the summation. Thus we now have

(9)

$E(R) = {R \over {K \cdot N^K}}\cdot\sum_{j=0}^{K-1}\left[{K \choose j}(N-1)^j\right]$

So close to that identity in equation (5)! We just need that $K-1$ on top of the summation to be a $K$ . So let's just add another term! We can then subtract by it too, so that we're not really adding anything.

(10)

$E(R) & = & {R \over {K \cdot N^K}}\cdot\left(\sum_{j=0}^{K-1}\left[{K \choose j}(N-1)^j\right] + {K \choose K}(N-1)^K - {K \choose K}(N-1)^K\right) \ & = & {R \over {K \cdot N^K}}\cdot\left(\sum_{j=0}^{K}\left[{K \choose j}(N-1)^j\right] - (N-1)^K\right) \ & = & {R \over {K \cdot N^K}} \left[((N-1) + 1)^K - (N-1)^K\right] \ \ & = & \ldots \ \ & = & R \cdot \left[ {{1 - \left({N-1 \over N}\right)^K } \over K}\right]$

Now the combinatorial explanation of that formula isn't as straightforward as formula (4) above, but you can now use a pocket calculator to compute your expected value instantly instead of having to use Java and its BigDecimal class and waiting hours.

Conclusion

In conclusion, given $N$ distinct possibilities to win, a total jackpot reward of $R$ , and $K$ total players, your expected value of a single ticket is:

(11)

$R \cdot \left[ {{1 - \left({N-1 \over N}\right)^K } \over K}\right]$

It would be considered "rational" to buy a lottery ticket if that expected value is greater than or equal to the cost of that ticket.

A few caveats:

Taking into account lump-sum value and taxes, the true value of the lottery jackpot is significantly less than advertised. You should figure that number out to compute your true expected value of playing the lottery.
1. However, for most people, anything over about $2 million is an essentially "infinite" amount of money. Figuring a very conservative investment return of about 5% a year, $2 million brings you $100,000 a year in interest alone. If they don't succumb to extreme lifestyle inflation, they can just park that money in the metaphorical bank and live off it forever. This may affect your expected value calculations.
2. That being said, I suggest: Never play the lottery as an investment strategy.
I couldn't readily find statistics on how many tickets are sold for the particular lottery that motivated my investigations: the Mega Millions. My guess is that the number of players actually depends on the jackpot reward. I.e., the higher the reward, the more players who play, thereby reducing your expected value even more.
I didn't take into account the various "secondary" prizes such as matching 5 numbers minus the Mega ball. Those are straightforward to compute, unless you live in California. For everyone else, these secondary prizes add about $0.18 to your expected value of a ticket (before taxes).
The biggest assumption that I took was that each player's choice was entirely independent of all other players. This isn't always the case! In particular, people often choose numbers that make up dates with special sentimental value to them as lottery numbers. Hence, if you play the lottery, to maximize your chances that you don't have to split the jackpot, play numbers bigger than 31.
I still bought a lottery ticket on Friday. And lost.

Thanks!

This investigation was far more fascinating to me than configurating f#$%ing JBoss, which has been my job at work for the last couple weeks. I needed a mental exercise like this to keep me from going insane! And besides, this is the kind of stuff that often goes on inside my head all the time. This one was just in a better form that I could post to the internet for mass consumption. I hope it was enjoyable, or at least educational! Thanks for reading!

Show Comments