A Summer 2015 Mathematics A To Z: graph

Graph. (As in Graph Theory)

When I started this A to Z I figured it would be a nice string of quick, two-to-four paragraph compositions. So far each one has been a monster post instead. I’m hoping to get to some easier ones. For today I mean to talk about a graph, as in graph theory. That’s not the kind of graph that’s a plot of some function or a pie chart or a labelled map or something like that.

This kind of graph we do study as pictures, though. Specifically, they’re pictures with two essential pieces: a bunch of points or dots and a bunch of curves connecting dots. The dots we call vertices. The curves we call edges. My mental model tends to be of a bunch of points in a pegboard connected by wire or string. That might not work for you, but the idea of connecting things is what graphs, and graph theory, are good for studying.

The Help Needed To Get to One

So, it’s established that my little series, representing the number of rides we could expect to get if we based re-riding on a fair coin flip, is convergent. So trying to figure out the sum will get a meaningful answer. The question is, how do we calculate it?

My first impulse is to see if someone else solved the problem first, for exactly the reasons you might guess. This is a case where mathematics textbooks can have an advantage over the web, really, since an introduction to calculus book is almost certain to have page after page of Common Series Sums. Figuring out the right combination of keywords to search the web for it can be an act of elaborate guesswork. Mercifully, Wikipedia has a List of Mathematical Series which covers my problem exactly. Almost.

Why Not Infinitely Many More Rides?

Returning to the Disaster Transport ride problem: by flipping a coin after each ride of the roller coaster we’d decide whether to go around again. How many more times could I expect to ride? Using the letter k to represent the number of rides, and p(k) to represent the probability of getting that many rides, it’s a straightforward use of the formula for expectation value — the sum of all the possible outcomes times the probability of that particular outcome — to find the expected number of rides.

Where this gets to be a bit of a bother is that there are, properly speaking, infinitely many possible outcomes. There’s no reason, in theory, that a coin couldn’t come up tails every single time, and only the impatience of the Cedar Point management which would keep us from riding a million times, a billion times, an infinite number of times. Common sense tells us this can’t happen; the chance of getting a billion tails in a row is just impossibly tiny, but, how do we know all these outcomes that are incredibly unlikely don’t add up to something moderately likely? It happens in integral calculus all the time that a huge enough pile of tiny things adds up to a moderate thing, so why not here?

Just One More Ride?

Given that we know the chance of getting any arbitrary number — let’s say k, because that’s a good arbitrary number — of rides in a row on Disaster Transport, using the scheme where we re-ride if the flipped coin comes up tails and stop if it comes up heads, the natural follow-up to me is: how many more rides can we expect? It’s more likely that we’d get one more ride than two, two more rides than three, three more rides than four; there’s a tiny chance we might get ten more rides; there’s a real if vanishingly tiny chance we’d get a million more rides, if Cedar Point didn’t throw us out of the park and tear the roller coaster down first.

How Many Last Rides?

So our scheme for getting a last ride in on Disaster Transport without knowing in advance it was our last ride was to flip a coin after each ride, and then re-ride if the coin came up tails. (Maybe it was heads. It doesn’t matter, since we’re supposing the coin is equally likely to come up heads as tails.) The obvious question is, how many times could we expect to ride? Or put another way, how many times in a row could I expect a flipped coin to come up tails, before the first time that it came up heads? The probability tool used here is called the geometric distribution.

When To Run For The Train

I mean to return to the subject brought up Monday, about the properties of things that don’t exist, since as BunnyHugger noted I cheated in talking briefly about what properties they have or don’t have. But I wanted to bring up a nice syllogism whose analysis I’d alluded to a couple weeks back, and which it turns out I’d remembered wrong, in details but not in substance.