## Two Principles of Mathematicsby robert

I was explaining something in probability theory to somebody last night, and I offhandedly said the following remark:

You know, it’s interesting what sorts of mathematics come up. For example, a usual exercise in undergraduate probability is the following: Flip a coin repeatedly until a heads comes up. What’s the expected number of coin flips required?

The person asked me what the number was, and I realized that I actually didn’t know. I gave an offhand guess of three, since we’re asking about a very particular sequence of coin flips (which has exponentially small density in the measure of all sequences of coin flips, and so it should be small). I sat down to work on it before bed, and rather quickly derived the following expression.

Let $X$ be the random variable in $\{1,2, \ldots\} = \mathbb{N}$ with the interpretation that $X = i$ if the $i$th coin flip in a sequence of flips is a head after $i-1$ tails. It’s straightforward to calculate $\Pr[X = i]$ — assuming we’re flipping a fair coin, the probability of getting $i-1$ tails followed by a single head is $(1/2)^{i}$. This means our expected value will be $E[X] = \sum_{i=1}^{\infty} i \Pr[X = i] = \sum_{i=1}^{\infty} i 2^{-i}.$

And, wait a minute, but this sum is not trivial to evaluate! At first I did what any self-respecting mathematician/computer scientist would do (i.e. HIT IT WITH YOUR HARDEST SLEDGEHAMMERULTRATOOL AND DYNAMITE THE PROBLEM TO ACCESS IT’S SWEET GOOEY INSIDES) and applied generating functions.

MMMMMMMMMMMMM

This (alas) didn’t work and I fell asleep dejected.

And I woke up with the cutest solution!

To begin, here’s a secret that your math teacher just won’t ever bloody tell you:

(1) Every inequality/sum/identity in the history of mathematics just comes from writing the same thing in two different ways.

Of course, with our friend hindsight bias this is obvious — once we have the identity $x = y$ in front of us, it’s easy to say “oh, well of COURSE $x = y$, it’s so obvious, duh!”.

Now, here is a second secret that your math teacher won’t ever bloody tell you:

(2) Every result ever obtained in mathematics can be broken down to a sequence of tiny, local, or otherwise easy steps.

When you say something as simple as I did in these two principles the questions of mathematics suddenly become significantly less daunting. To illustrate both of these principles, I’ll use them to evaluate our sum $\sum_{i=1}^{\infty} i2^{-i}$ from the probabilistic puzzle above. First, let’s recall what an infinite sum actually is, as it’s kind of easy to forget: the sum

$\displaystyle \sum_{i=1}^\infty i2^{-i}$

is really defined as a limit of partial sums

$\displaystyle \lim_{n \rightarrow \infty} \sum_{i=1}^n i2^{-i}.$

So, applying our first principle from above, we’re going to rewrite $\sum_{i=1}^n i2^{-i}$ as another function $f(n)$ so that we can actually evaluate the limit above.

Now, how do we do this? First, just to simplify notation for ourselves, let $f(n) = \sum_{i=1}^n i2^{-i}.$ Let’s apply our second principle from above — what are some really stupendously obvious facts about the sum $f(n) = \sum_{i=1}^n i2^{-i}$? Well, since it’s a frigging sum, we know that

$\displaystyle f(n+1) = \sum_{i=1}^{n+1} i2^{-(i+1)} = f(n) + (n+1)2^{-(n+1)}.$

Alright, here is a start. If we can apply our first principle to the sum $f(n+1)$ and write it down in another way then maybe we’ll end up somewhere interesting. Well, what about this sum? Let’s write it down explicitly, so that we can actually see some of the structure of the terms. I’m also going to make the substitution $r = 1/2$ and instead write

$\displaystyle f(n) = \sum_{i=1}^{n} ir^i.$

Time for a side rant. Now, a math teacher, jerks as they are, will tell you to do this kind of substitution because your result is more general (or, even worse, tell you nothing at all, leaving you swimming in a soup of variables/indeterminates with no flotation device).

Everyone in any math class, ever. THE OCEAN IS VARIABLES

As usual, this is the correct information but stated in a way so that humans can’t understand it. Another way to say this “generality” assumption is, simply, people hate magic numbers! Notice that NOTHING! about the sums we’ve considered so far have needed the 2 to be there (other than the fact that our problem happens to be about coins). Well, if there’s no reason for it to be there, then why should it be there? The sum $\sum_{i=1}^n ir^i$ is even a bit easier to swallow visually. Anyways, side rant over.

Back on track, here are the sums $f(n)$ and $f(n+1)$, both written down explicitly:

$\displaystyle f(n) = r + 2r^2 + 3r^3 + \cdots + nr^n$

$\displaystyle f(n+1) = r + 2r^2 + 3r^3 + \cdots + nr^n + (n+1)r^{n+1}.$

Well, recall that I said that we were trying to rewrite $f(n+1)$ in a way other than

$\displaystyle f(n+1) = f(n) + (n+1)r^{n+1}.$

Applying our first principle — and this is really the leap of intuition — let’s just transform $f(n)$ into $f(n+1)$ in another way! How? Well, multiply $f(n)$ by $r$ and compare it to $f(n+1)$:

$\displaystyle rf(n) = r^2 + 2r^3 + \cdots + (n-1)r^n + nr^{n+1}.$

$\displaystyle f(n+1) = r + 2r^2 + 3r^3 + \cdots + nr^n + (n+1)r^{n+1}.$

We’ve almost got $f(n+1)$! The only thing that’s missing is a single copy of each term in the sum! Phrased mathematically, we now have the identity

$\displaystyle f(n+1) = rf(n) + (r + r^2 + r^3 + \ldots + r^n + r^{n+1}).$

Now, the sum $\sum_{i=1}^n r^i$ is a geometric sum which has a simple formula (fact: this simple formula can be derived in a way similar to our current investigation):

$\displaystyle \sum_{i=1}^n r^i = \frac{1 - r^{n+1}}{1 - r} - 1.$

So, substituting in this new simple formula gives

$\displaystyle f(n+1) = rf(n) + \frac{1 - r^{n+2}}{1 - r} - 1$

and then, finally finishing our application of the first principle, we can apply our early “stupid” identity for $f(n+1)$ and get

$\displaystyle f(n) + (n+1)r^{n+1} = rf(n) + \frac{1 - r^{n+2}}{1 - r} - 1.$

The rest is algebra/boilerplate. Collecting the $f(n)$ terms on the left hand side, we get

$\displaystyle (1- r)f(n) = \frac{1 - r^{n+2}}{1 - r} - 1 - (n+1)r^{n+1},$

then dividing both sides by $(1-r)$ finally gives

$\displaystyle f(n) = (1-r)^{-1}\left(\frac{1 - r^{n+2}}{1 - r} - 1 - (n+1)r^{n+1}\right).$

Taking the limit as $n \rightarrow \infty$ and using our knowledge that $r = 1/2 < 1$, we see that the terms involving $r^{n+1}$ will disappear. This leaves

$\displaystyle \lim_{n \rightarrow \infty} f(n) = \frac{1}{1-r}\left(\frac{1}{1 - r} - 1\right).$

Substiting in $r = 1/2$, we get

$\displaystyle \lim_{n \rightarrow \infty} f(n) = 2(2 - 1) = 2.$

And we’re done. In expectation, you will see a heads after 2 coin flips.

You see, math is not mystical. Unless you’re a Newton or an Euler (viz. an absolutely genius), math proceeds pretty much the same for everybody. There are underlying principles and heuristics that help you do math that every established mathematician actually uses — the secret is that no one ever tells you them. Of course, I have a sneaking suspicion that this due to the fact that our high school math teachers don’t actually understand the principles themselves (while this may seem like a bit of an attack, I did graduate with people who were going to be math teachers. Most of those people should not have been math teachers).

## CGN2-ROG Followupby Steven

Additionally, if the router (in bridge mode) is plugged into any other type of outlet such as a power bar or splitter, it will not properly renew the IP.

## That moment…by Steven

…you realize if anyone walked in and saw you, that they would run away screaming.

## Getting Samsung Galaxy Nexus to install Googles drivers.by scirvir

Holy crap cshouse! Posts aplenty,

the guts

So I recently been tasked with the job of writing some benchmarking tools for the iphone4 for a game that I am currently porting. Since we are porting from some insanely old engine to unity3d, I’m building these tools with that. More on this later… possibly… doubtfully. Anyways since Unity3d just gave out a castrated version of there android + ios licences I figured I would also try to run it on my galaxy nexus. Naturally as with all my previous android ADT/SDK experience nothing worked immediately.
Firstly just as a heads up Unity as of june 5th 2013, hates revision 22 of the ADT/SDK so you should us this ###insert link to patch### I’ll do this once I get the files put into tho stockpile. lols on June 6th unity released a update to version 4.1.4, this update resolves the issues with revision 22 of the android SDK.

INSERT MONTAGE OF LATE NIGHT COMPUTER MONITOR RADIATION, AND FRANTIC GOOGLE SEARCHING.

So here is a quick study of what you probably need to do without going into resetting pathnames, and all that other stuff I immediatly disregarded as overkill, because where ever you read that you need to install the drivers through windows device manager.

what they really mean is don’t use the windows feature I have the drivers in a folder on my computer obviously, they mean,
use this other button, that sais I want to select from a list of drivers on my computer which I naturally assumed was the wrong one, and thinking to myself, “I know exactly what folder those drivers are in” I kept using the first one, which was pointed right at the ~/somefilepath>/android/skd/extras/google/usb-something.

Inwhich you will be givin a terrible list of things that are not your phone but don’t fret, cliq on the Have disk button, then browse to the url where the drivers are.

Then browse to the desired path at ~/somefilepath>/android/skd/extras/google/usb-something. , and lo and behold, your drivers will show up in a list, I mashed install on the first one out of excitement, and there we have it drivers for my Galaxy Nexus finally installed.

No word of a lie, I think I rather be using ndiswrapper to fix wireless… thats not true.

I don’t know if because I am not really a windows power user, this doesn’t seem like an obvious way to install drivers, mainly when you are given the option to point at a file, but maybe the blame falls on Google for packaging it non-standard. Either way I’m glad that it’s working now.

Night folks.

## Bridge Mode Workaround for Rogers Router CGN2-ROGby Steven

csHouse has turned to the dark(er) side of canadian internet providers, and is now running on the Rogers Extreme High Speed Internet Package which boasted a modest 35Mbps down, 3Mbps up.

Not too shabby right? Not quite FiberOP, but will get everything up and running. Good stuff.

HOWEVER!

The service tech gave me a box containing their latest model of modem/router, and out popped the CGN2-ROG, looking like it was steeped in the 90s, and had plenty of ‘tude.

180 KICKFLIP

Flashing it’s massive, pointless LEDs, it sputtered to life and began sending and receiving data slower then I could have delivered it by hand. Great.

It turns out this badboy is completely incapable of routing, so, lets just offload that task onto a much better router.

IF YOU ARE HERE FROM GOOGLE, AND FOUND THIS SITE BY TYPING IN A WORD SALAD OF RAGE AND ROUTING ISSUES, YOU CAN BEGIN READING NOW.

So, you’ll need your crappy CGN2-ROG, another router (In my case, it was the RT-N56U), and an ethernet cable (CAT6) to connect them.

2. Credentials are cusadmin/password by default, because it’s a magical star child who wants to be different.
3. If you can’t log in, factory reset it, or use the usb unlocker they may or may not have been included with the device.
4. Go to 192.168.0.1/user/setup-capability.asp
5. Disable everything, hit apply. This will place the router into bridge mode. You will NOT be able to access the router now. If you need to, I’d recommend factory reset. It’s possible to directly connect a machine to the router, and access the router through it’s external IP, but just…don’t do that.
6. Set up your second router, plug the ethernet cable into the LAN port 1 of the CGN2-ROG, and into the WAN port of the new router. Turn it on.
7. You should be good to go, and can treat your new router as the main router. For all intents and purposes, the CGN2-ROG is now just a fancy internet box.

You should notice an immediate improve in speed and stability, and are free to use any router you want.

DING DING DING KO!

## Kobo Mini Protipby robert

Here I was, minding my own business, when I picked up my Kobo Mini to do some reading and suddenly I heard a rattle.

Not in my house, I thought.

So, off comes the back, and here is what greeted me:

Considering that the Kobo Mini does not claim to have extensible memory, I popped out the SD card, tried turning the e-reader back on, and was (in retrospect, a little too) surprised to discover that nothing happened. I guess it’s cheaper to use an SD card for secondary memory and just not tell your customers that it’s there. I mean, most people would beat the crap out of this tiny plastic rectangle while trying to get the back off — not to mention the intense technical skill that goes into copying the OS files from one SD card to a slightly larger one.

Honestly, what is this piece of trash.

It appears that the tiny piece of plastic which makes the Kobo’s nigh-unseeable LED slightly more visible had broken off and was tap-dancing on the motherboard. Sigh.

## The theology of retributionby Emily

This may be the GALLONS of coffee… but I think the theology of retribution is a paradox. Neat eh? Like, the theology of retribution relies on the assumption that when God created the cosmos in the beginning (bere’shit…heh. Bible joke…), He finished it. A finished creation implies some degree of self-sufficiency based on established order. However, based on the existence of chaos in the world (Job 38:26-27), and things like innocent suffering and evil (Genesis 4), it is reasonable to conclude that God must take an active role in maintaining his creations and the balance between order and chaos (this is further explored in Job 38-41, see Behemoth and Leviathan). This suggests that creation is an ongoing, fluid process. The theology of retribution holds that the good are rewarded and the wicked are punished. It is DEPENDENT on a view of order in the world, and therefore, a completed or finished creation. But, as is overwhelmingly evident in the Book of Job, the traditional view is that the theology of retribution is an active act of God, He will not (in theory) harm the pious. SO, paradoxically, the theology of retribution depends on the view that the universe is self-sufficient, but also that God is the chess master. My head is spinning.

## Pet Peeves and Inductive Horsesby robert

Put your math pants on ladies and gentleman, this one’s gonna be a vomitbuster.

This post will be about mathematical induction (if you aren’t familiar with induction, it’s a simple and powerful proof technique that is ubiquitous in mathematics. For the intuitive picture, go here). Well, it will sort of be about mathematical induction. This post will use mathematical induction to help express my hatred for incomplete explanations. We will prove the following theorem (anybody who has seen induction will have seen this theorem and the proof before.)

Theorem All horses are the same colour.

Proof. We will proceed by induction on the size of the set of horses. Suppose that we have a single horse. Then, clearly all (one) of our horses have the same colour. Assume inductively that for every collection of n horses, all the horses in A have the same colour. We will show that in every collection of n+1 horses, all the horses have the same colour.

Let H = {h(1), h(2), …, h(n+1)} be a collection of n+1 horses. Then we can choose two sub-collections of H: A = {h(1), h(2), …, h(n)} and B = {h(2), h(3), …, h(n+1)}. By our inductive assumption, all the horses in A and B have the same colour. It follows that the colour of h(1) is the same as the colour of h(2) which is the same as the colour of h(n+1), and so all the horses in H must have the same colour. Q.E.D.

Now, clearly all horses are not the same colour.

Not the same colour.

Let’s name those two horses Flowerpot and Daffodil. Most explanations of why the above theorem is wrong go like this:

Teacher: Clearly, the set of horses P = {Flowerpot, Daffodil} is a contradiction to our theorem. So, class, what have we learned? When you’re doing induction, always check your base cases!

Right, but quite an unsatisfying explanation. This explains why the theorem is wrong. But why is the proof wrong? That’s actually a bit of a head scratcher.

Go on. Do it. Scratch that head. Get them lices out.

I mean, we followed all the steps of mathematical induction — we chose a base case, we proved that theorem was correct. We made an inductive assumption for some n, and using the assumption we proved the theorem holds for n+1. Where’s the problem?

Well, lets look at our proof. We have a set H of size n+1, which clearly can be done. We chose two subsets of H, A and B, both of size n. Also can be done. Next, we apply the inductive hypothesis to A and B, and so all the horses in A and B are the same colour. Now, since A and B have a non-empty intersection… Ahah. There’s the problem. What if n = 1? Then H = {h(1), h(2)}, and A = {h(1)}, B = {h(2)}. But then A and B have an empty intersection. If A is the set containing Flowerpot and B is the set containing Daffodil, then we cannot say that Flowerpot is the same colour as Daffodil. Okay! Great!

I think that this is fundamentally different from the broad sweep of “You didn’t check all your base cases”. This is really saying your logic used in the inductive step does not apply to all of the base cases. It’s subtle, but a very important difference. The pedagogical conclusion: teachers, think hard about what you’re presenting. When you think you understand something, it turns out that you usually don’t.

One more thing. In a way, the problem really comes from how I wrote H in the first place! Remember I wrote H = {h(1), h(2), …, h(n+1)}. When performing the partitioning of H into A = {h(1), h(2), …, h(n)} and B = {h(2), h(3), …, h(n+1)}, this suggests that the intersection of A and B is non-empty. This is an interesting instance of the form of our text affecting the content of our text (at least to us). This is an idea I will hopefully return to in later posts.

Finally, a moment of silence. Searching for an image of a head scratcher led me deep into a rabbit hole from which I may never return.

A nose straightener.

## Minecraft Tomfooleryby robert

As earlier mentioned by Soucy, we are running a vanilla Minecraft server here on cshouse. Here are two instances of balls-out randomness that probably have something to do with the fact that we keep the server up to the current snapshot (instability YAY!).

My personal favorite — squid in a minecart. We have a stupendously complicated minecart system on the server connecting the Cold Hell Lake to Jungle Prison.

The minecart runs through a low point before it reaches the Jungle Prison. For whatever reason, a squid spawned in the river and hopped into this minecart as it went by. Hilarious.

Next: The recent snapshot introduced pumpkin pie. For whatever reason, my version of Minecraft (snapshot 12w37b, running on Ubuntu Linux 12.04) couldn’t handle the pumpkin pie. Whenever I opened a box containing it, my client would crash. And when Soucy held one — well, just look at what happened:

Note the upside down nametag, invisible pumpkin pie in Soucy’s hand, and the floating, upside down cows in the background. Other fun glitches involved upside down torch fire dancing by, and sprinting upside down jungle cats!

So much fun WASTING VALUABLE TIME.

## A Roasters Haikuby Steven

Fall begins with bitter brew

Hot, cold or lukewarm makes no difference