Ouch, this one makes my head hurt
Today’s post will be written in short pieces, kind of like the elegy, but shorter. And on random topics. So, kind of like it, but not really. Kind of like how Gonzo is kind of like a turkey, but not really. Anyway.
I am sitting in an airport. On line for Southwest airlines. I'm an A, yes. There is, however, an infinite amount of fascinating human behavior in airports. First, I’ve noticed a new, interesting Southwest line behavior. When the line is near chairs, people sit in the chairs rather than sitting on the line itself.
Here’s the rub: Are they, in fact, in line? Should I walk up and sit ON the line, at the front? Or should I sit somewhere back? I always struggle with this decision. Today, I sat on the chairs, in order. And some guy walked up to the front and stuck his bags at the front of the line. And THEN he sat down on the chairs. Hmm. Methinks he knows he just cut and yet he doesn’t care. So I moved out into the middle of the “line”, on position with where I was on the chairs, and sat on the floor to type. Meets both my need for fairness – please don’t walk in front of me and pretend you didn’t know – and honesty – I am not moving myself forward in the line.
The whole thing seems pointless anyway – there is one cool exit row seat, and 3 normal exit row seats. Then the rest of the plane is one-third aisles and one-third windows. Thus, two-thirds of all seats on the plane are desirable. And they are all more or less the same. Thus, the first ~4 people in the A line might be special – as they might get cooler exit seats – but after that, everyone in A is going to get a seat they like, and probably as much bin space as they can consume. So why do I care about someone walking in front of me? I'm not in the first four! I guess I care because it’s against the rules, and, lord knows, rules are important to me.
By the way, there is now an active queue behind me for the A line. I guess social pressure works?
Continuing on in the vein of interesting airport behaviors. A woman was walking, with purpose, down the left side of the hallway – against “traffic” as it were. I was walking up towards her – on the right side, from my perspective. She was looking resolutely to her right – away from the way she was walking. About 10 feet away, as I closed on her rapidly – I stride quickly – I noticed her lack of attention, and stopped. She proceeded to walk full-on into me. And snapped at me. Umm, lady? I was standing still, with both feet planted. I think that’s an offensive foul. And, regardless, try looking in the general direction you are moving!
I was people watching, as is my wont, and I saw the funniest interaction ever, outside of a bad sitcom. A young woman – maybe in her 20s – was on the phone, not quietly. She used a curse word (yowsers! Kids these days!). Anyway, she was sitting down in a line of chairs, across from another line of chairs, about 6 feet away. There was a mother, with a little girl – maybe 10 or so – sitting on those chairs. Upon utterance of the curse, the mother looked up with a shocked look, and clapped both her hands over her daughters’ ears.
You’re kidding right?
And it gets better. Mommy then proceeded to lecture the 20 year old about her foul language and how it will have a negative impact on the youth of tomorrow. She even used the phrase “rotting morals”. Wow. Ok, I hate cell yell. And I'm sometimes embarrassed by my trucker mouth. And yet it never occurred to me to tell random people to cover their ears? And, lady, do you think your daughter has never heard such words before? The little girl noticed me, noticing them, and blushed VERY bright red. I'm guessing that girl is going to react, just a little bit, against mommy’s dictates as soon as she can. Is that trouble I hear? Hmm. And I really admire people who feel like it is ok for them to lecture others on their behavior, publicly, without invitation. “I'm so pious that I must educate you, even against your will.” Almost like missionaries who convert by sword.
Remember, really, no one ever expects the Spanish Inquisition, but do you think Torquemada is on God’s good list for “converting” all those people? Yeah, me neither. But apparently, my opinion doesn’t matter – the rise of holier-than-thou continues, across my home country, unabated as far as I can tell.
And extra points to everyone who notices I was just being holier-than-they.
Moving right along.
An update: on the plane now. The guy who walked to the front of the line took the really good seat, with no apparent shame, at all. I'm in the exit row aisle. There are two very happy women sitting next to me. They are laughing, and pretty funny. So far, I’ve been “honey”-ed twice, and had my shoes complimented three times. They must have been in the Bay Area partying…
Speaking of which, it’s a small world. I was wandering relatively aimlessly though the airport, trying to figure out if I could hop on the earlier flight, and I noticed a cute woman walking in the other direction. Ok, cool – didn’t pay that much attention, even though I'd noticed she’s cute. As she gets closer, she calls my name – turns out she’s a friend of mine. It’s a small world. Who runs into friends in the airport? Oakland is a small airport, but not THAT small. Anyway, was nice to see her.
OK, want a quick peek into my weird mind? I was standing in line waiting to go through security, reviewing this week’s interactions with some of my friends. I have a friendly pseudo-wager with a friend related to the number of games required to close out the NBA finals. I asserted it would require 5 games – 4 to 1 in favor of one team. (It’s a best of 7 series, not the World Cup, gang). My friend thinks I'm an idiot, for any number of reasons, including this assertion. He thinks it’s 7 games (indicating a 4-3 game score, although we both think the same team will win). So, there’s a “wager”, I guess.
Now, what are the odds, statistically, that I'll “win”?
The math behind this kept my brain occupied while the TSA was making me safe. For 30 minutes. And I can’t figure it out. So let’s examine my poor math skills, shall we?
OK, how many ways can there be a win in a best of 7 series? Let’s assert there are two teams, one called A, and the other B. A could sweep the series (win 4-0), or be swept (B wins 4-0). Similarly, each could win in 5 games (4-1 for A, or 4-1 for B). Or in 6 games (4-2 A or 4-2 B), or either could win in 7 games (4-3 A or 4-3 B). Thus, there are 8 independent outcomes possible.
// Author’s note: IANAL, but I think it’s not legal to place monetary wagers on professional sports in my home state. I obviously didn’t break that law, if in fact it is a law. This is why I’ve been typing “bet” instead of bet. For the sake of verbal brevity, I will henceforth omit the quotations marks around “bet” or “wager”. You all understand the context, I think. //
Ok, I bet that one of those 8 outcomes would appear. My friend, essentially, bet on the other 7. Clearly he has the statistical advantage. Since placing this bet, team A won game 1. Thus, in this world, A can’t be swept in this series. There are only 7 outcomes that remain. And he’s still up 6 to 1.
There’s another game today, which should remove more degrees of freedom. If A wins, the game score would be 2-0 A, so there couldn’t be a 4-1 B outcome. (But there are still 6 possible outcomes: 4-0 A, 4-1 A, 4-2 A, 4-3 A, 4-3 B, and 4-2 B.)
However, if B wins today, it’s 1-1, so we know A can’t sweep. (Remaining possibilities are 4-1 A, 4-2 A, 4-3 A, 4-1 B, 4-2 B, 4-3 B; still 6 possibilities remain.) Each game removes at least one degree of freedom.
However, it can’t be only one degree of freedom. We need to lose more – because a 4-0 outcome occurs in 4 games, and at that moment there are NO other outcomes possible. Thus, in a 4 game sweep, we have removed all but one degree of freedom. My current model has each game removing one degree of freedom; in this model, after 4 games there should still be 4 options. Whoops.
So, clearly, I screwed something up. I think my game today only eliminated one degree of freedom. Maybe more get eliminated as we go on? Let’s try another game.
If today’s game yields a 2-0 situation, what would the NEXT game do? It could be an A win, giving us 3-0. At that point, the only options left are 4-3 B, 4-0 A, 4-1 A, 4-2 A, or 4-3 A. 5 options. (The options remaining if B wins that next game are left as an exercise for the reader.)
Darn, another game, only 1 degree lost.
Now, in a 3-0 world, the next game is a doozy. Either you end the series (A wins, 4-0), or B wins (3-1 B). If B wins, there are fewer possibilities (4-1 A, 4-2 A, 4-3 A, or 4-3 B).
How did we go from 5 options to 1 (or 4)?
This is an information theory problem, where is Claude Shannon when you need him? OK, well, he’s dead, but work with me here, I'm being metaphorical.
Anyway, the possibilities remaining are basically entropy – the amount of information left in the expression. Entropy is a critical measure in lots of things, including codes, cryptography, and error correction. Regardless, back to my problem. Somehow there is more information added, in a nonlinear amount, as the games go on.
Ok, let’s move to data structures for a minute. Imagine the space of game scores as a tree, with vortexes being games. The root node was game one, with a 0-0 game score. Each node has two children – because there are two possible outcomes (A wins or B wins), but each node has a different game score. When the series is over, there are no more games, thus no more nodes, just children – called terminal leaf nodes. These leaf nodes are the final game scores – there are no more possibilities, so no more nodes. These are the outcomes we have been talking about.
To an AI person (like your truly), this is a tree search problem. Basically, we are pruning the tree – each game renders part of the tree irrelevant.
To me, at any rate, the data structure helps me see the problem a bit differently.
The tree isn’t the same depth across it – depth is a measure of how many nodes there are between the root and the leaves. In a 4-0 sweep, the tree depth is just 4. In a 4-3 victory, the tree is 7 nodes deep. By definition, the entropy must be a function of how deep the tree is underneath you at any given moment.
In a 3-0 game score, the tree is pretty shallow under you – on one side, your child is a leaf. On the other, the leaves are pretty close (although there is a 4 deep tree below you over there).
If I were slightly smarter, I could figure this out. I need a function that is nonlinear to calculate entropy – weirdly nonlinear, actually, since the answer itself is not uniform (it’s choppy, you move from 5 options to 1 in one step).
Hmm, ok I think I will cave here, and go back to the other part of the math that was occupying my mind in line – what’s the formula for figuring out how many leaf nodes there should be in the tree?
In general, the way to figure out how many options there are for some game is a pretty simple function. For example, how many possibilities are there if you have 3 balls, each a different color, and you select one randomly? The first selection has three options, the second has only two options (since you already took one out) and the final choice has only one option. In probability theory, the total probabilities are equal to the multiplication of each probability. In this case, the total number of options (yes, slightly different, but close enough for now) is equal to 3 * 2 * 1, or 3 factorial (commonly written as 3!).
But if you are taking more than one object at a time it is more complicated. For example, let’s go back to the colored balls, and this time pick up two at a time. Now how many different ways are there to “take three balls, two at a time”?
Let’s work through an example assuming the balls are Red, Blue, and Green. Remember the task, you are going to grab two balls – the question is how many different outcomes there could be? You could get Red and Blue, or Blue and Green, or Red and Green.
Ok, so there are three different ways to take 3 items, 2 at a time.
This is not 3 factorial, right? But there is a formula for n items, taken k at a time. The formula is n! / (k * (n-k)! ) – so in this case 3! / (2 * (3-2)!) == 3! / (2*1) == 3!/2 == (3 * 2 * 1 ) == 3 * 1 == 3.
Sweet.
So, my real question – how many leaf nodes are there in a series? It’s not 7 factorial. Nor is it 7, taken two at a time (which would be 21, I think). It can’t be, because large parts of the random space of combinations aren’t possible – for example, given numbers 1 to 7, taken two at a time, you could draw 7 and 6, which isn’t a possible game score.
So I spent my time in the security line thinking about this problem, and my time on the plane writing about it, and no time actually doing the math. So, OtherEnders, this problem like so many others described in these pages, is left to you to solve. I can’t wait.
And no, this isn’t one of my interview questions.
Well, I’ve arrived in the Sunny Southwest. It’s warm here, and warmth is not conducive to math thinking in my head. So I'm out. I'm going to go ride a motorcycle, have a drink, and see my friend. I'll play my music too loud, and think peaceful thoughts. I will feel the Spirit from the Desert.
At the center, I hope you are well.
I am sitting in an airport. On line for Southwest airlines. I'm an A, yes. There is, however, an infinite amount of fascinating human behavior in airports. First, I’ve noticed a new, interesting Southwest line behavior. When the line is near chairs, people sit in the chairs rather than sitting on the line itself.
Here’s the rub: Are they, in fact, in line? Should I walk up and sit ON the line, at the front? Or should I sit somewhere back? I always struggle with this decision. Today, I sat on the chairs, in order. And some guy walked up to the front and stuck his bags at the front of the line. And THEN he sat down on the chairs. Hmm. Methinks he knows he just cut and yet he doesn’t care. So I moved out into the middle of the “line”, on position with where I was on the chairs, and sat on the floor to type. Meets both my need for fairness – please don’t walk in front of me and pretend you didn’t know – and honesty – I am not moving myself forward in the line.
The whole thing seems pointless anyway – there is one cool exit row seat, and 3 normal exit row seats. Then the rest of the plane is one-third aisles and one-third windows. Thus, two-thirds of all seats on the plane are desirable. And they are all more or less the same. Thus, the first ~4 people in the A line might be special – as they might get cooler exit seats – but after that, everyone in A is going to get a seat they like, and probably as much bin space as they can consume. So why do I care about someone walking in front of me? I'm not in the first four! I guess I care because it’s against the rules, and, lord knows, rules are important to me.
By the way, there is now an active queue behind me for the A line. I guess social pressure works?
Continuing on in the vein of interesting airport behaviors. A woman was walking, with purpose, down the left side of the hallway – against “traffic” as it were. I was walking up towards her – on the right side, from my perspective. She was looking resolutely to her right – away from the way she was walking. About 10 feet away, as I closed on her rapidly – I stride quickly – I noticed her lack of attention, and stopped. She proceeded to walk full-on into me. And snapped at me. Umm, lady? I was standing still, with both feet planted. I think that’s an offensive foul. And, regardless, try looking in the general direction you are moving!
I was people watching, as is my wont, and I saw the funniest interaction ever, outside of a bad sitcom. A young woman – maybe in her 20s – was on the phone, not quietly. She used a curse word (yowsers! Kids these days!). Anyway, she was sitting down in a line of chairs, across from another line of chairs, about 6 feet away. There was a mother, with a little girl – maybe 10 or so – sitting on those chairs. Upon utterance of the curse, the mother looked up with a shocked look, and clapped both her hands over her daughters’ ears.
You’re kidding right?
And it gets better. Mommy then proceeded to lecture the 20 year old about her foul language and how it will have a negative impact on the youth of tomorrow. She even used the phrase “rotting morals”. Wow. Ok, I hate cell yell. And I'm sometimes embarrassed by my trucker mouth. And yet it never occurred to me to tell random people to cover their ears? And, lady, do you think your daughter has never heard such words before? The little girl noticed me, noticing them, and blushed VERY bright red. I'm guessing that girl is going to react, just a little bit, against mommy’s dictates as soon as she can. Is that trouble I hear? Hmm. And I really admire people who feel like it is ok for them to lecture others on their behavior, publicly, without invitation. “I'm so pious that I must educate you, even against your will.” Almost like missionaries who convert by sword.
Remember, really, no one ever expects the Spanish Inquisition, but do you think Torquemada is on God’s good list for “converting” all those people? Yeah, me neither. But apparently, my opinion doesn’t matter – the rise of holier-than-thou continues, across my home country, unabated as far as I can tell.
And extra points to everyone who notices I was just being holier-than-they.
Moving right along.
An update: on the plane now. The guy who walked to the front of the line took the really good seat, with no apparent shame, at all. I'm in the exit row aisle. There are two very happy women sitting next to me. They are laughing, and pretty funny. So far, I’ve been “honey”-ed twice, and had my shoes complimented three times. They must have been in the Bay Area partying…
Speaking of which, it’s a small world. I was wandering relatively aimlessly though the airport, trying to figure out if I could hop on the earlier flight, and I noticed a cute woman walking in the other direction. Ok, cool – didn’t pay that much attention, even though I'd noticed she’s cute. As she gets closer, she calls my name – turns out she’s a friend of mine. It’s a small world. Who runs into friends in the airport? Oakland is a small airport, but not THAT small. Anyway, was nice to see her.
OK, want a quick peek into my weird mind? I was standing in line waiting to go through security, reviewing this week’s interactions with some of my friends. I have a friendly pseudo-wager with a friend related to the number of games required to close out the NBA finals. I asserted it would require 5 games – 4 to 1 in favor of one team. (It’s a best of 7 series, not the World Cup, gang). My friend thinks I'm an idiot, for any number of reasons, including this assertion. He thinks it’s 7 games (indicating a 4-3 game score, although we both think the same team will win). So, there’s a “wager”, I guess.
Now, what are the odds, statistically, that I'll “win”?
The math behind this kept my brain occupied while the TSA was making me safe. For 30 minutes. And I can’t figure it out. So let’s examine my poor math skills, shall we?
OK, how many ways can there be a win in a best of 7 series? Let’s assert there are two teams, one called A, and the other B. A could sweep the series (win 4-0), or be swept (B wins 4-0). Similarly, each could win in 5 games (4-1 for A, or 4-1 for B). Or in 6 games (4-2 A or 4-2 B), or either could win in 7 games (4-3 A or 4-3 B). Thus, there are 8 independent outcomes possible.
// Author’s note: IANAL, but I think it’s not legal to place monetary wagers on professional sports in my home state. I obviously didn’t break that law, if in fact it is a law. This is why I’ve been typing “bet” instead of bet. For the sake of verbal brevity, I will henceforth omit the quotations marks around “bet” or “wager”. You all understand the context, I think. //
Ok, I bet that one of those 8 outcomes would appear. My friend, essentially, bet on the other 7. Clearly he has the statistical advantage. Since placing this bet, team A won game 1. Thus, in this world, A can’t be swept in this series. There are only 7 outcomes that remain. And he’s still up 6 to 1.
There’s another game today, which should remove more degrees of freedom. If A wins, the game score would be 2-0 A, so there couldn’t be a 4-1 B outcome. (But there are still 6 possible outcomes: 4-0 A, 4-1 A, 4-2 A, 4-3 A, 4-3 B, and 4-2 B.)
However, if B wins today, it’s 1-1, so we know A can’t sweep. (Remaining possibilities are 4-1 A, 4-2 A, 4-3 A, 4-1 B, 4-2 B, 4-3 B; still 6 possibilities remain.) Each game removes at least one degree of freedom.
However, it can’t be only one degree of freedom. We need to lose more – because a 4-0 outcome occurs in 4 games, and at that moment there are NO other outcomes possible. Thus, in a 4 game sweep, we have removed all but one degree of freedom. My current model has each game removing one degree of freedom; in this model, after 4 games there should still be 4 options. Whoops.
So, clearly, I screwed something up. I think my game today only eliminated one degree of freedom. Maybe more get eliminated as we go on? Let’s try another game.
If today’s game yields a 2-0 situation, what would the NEXT game do? It could be an A win, giving us 3-0. At that point, the only options left are 4-3 B, 4-0 A, 4-1 A, 4-2 A, or 4-3 A. 5 options. (The options remaining if B wins that next game are left as an exercise for the reader.)
Darn, another game, only 1 degree lost.
Now, in a 3-0 world, the next game is a doozy. Either you end the series (A wins, 4-0), or B wins (3-1 B). If B wins, there are fewer possibilities (4-1 A, 4-2 A, 4-3 A, or 4-3 B).
How did we go from 5 options to 1 (or 4)?
This is an information theory problem, where is Claude Shannon when you need him? OK, well, he’s dead, but work with me here, I'm being metaphorical.
Anyway, the possibilities remaining are basically entropy – the amount of information left in the expression. Entropy is a critical measure in lots of things, including codes, cryptography, and error correction. Regardless, back to my problem. Somehow there is more information added, in a nonlinear amount, as the games go on.
Ok, let’s move to data structures for a minute. Imagine the space of game scores as a tree, with vortexes being games. The root node was game one, with a 0-0 game score. Each node has two children – because there are two possible outcomes (A wins or B wins), but each node has a different game score. When the series is over, there are no more games, thus no more nodes, just children – called terminal leaf nodes. These leaf nodes are the final game scores – there are no more possibilities, so no more nodes. These are the outcomes we have been talking about.
To an AI person (like your truly), this is a tree search problem. Basically, we are pruning the tree – each game renders part of the tree irrelevant.
To me, at any rate, the data structure helps me see the problem a bit differently.
The tree isn’t the same depth across it – depth is a measure of how many nodes there are between the root and the leaves. In a 4-0 sweep, the tree depth is just 4. In a 4-3 victory, the tree is 7 nodes deep. By definition, the entropy must be a function of how deep the tree is underneath you at any given moment.
In a 3-0 game score, the tree is pretty shallow under you – on one side, your child is a leaf. On the other, the leaves are pretty close (although there is a 4 deep tree below you over there).
If I were slightly smarter, I could figure this out. I need a function that is nonlinear to calculate entropy – weirdly nonlinear, actually, since the answer itself is not uniform (it’s choppy, you move from 5 options to 1 in one step).
Hmm, ok I think I will cave here, and go back to the other part of the math that was occupying my mind in line – what’s the formula for figuring out how many leaf nodes there should be in the tree?
In general, the way to figure out how many options there are for some game is a pretty simple function. For example, how many possibilities are there if you have 3 balls, each a different color, and you select one randomly? The first selection has three options, the second has only two options (since you already took one out) and the final choice has only one option. In probability theory, the total probabilities are equal to the multiplication of each probability. In this case, the total number of options (yes, slightly different, but close enough for now) is equal to 3 * 2 * 1, or 3 factorial (commonly written as 3!).
But if you are taking more than one object at a time it is more complicated. For example, let’s go back to the colored balls, and this time pick up two at a time. Now how many different ways are there to “take three balls, two at a time”?
Let’s work through an example assuming the balls are Red, Blue, and Green. Remember the task, you are going to grab two balls – the question is how many different outcomes there could be? You could get Red and Blue, or Blue and Green, or Red and Green.
Ok, so there are three different ways to take 3 items, 2 at a time.
This is not 3 factorial, right? But there is a formula for n items, taken k at a time. The formula is n! / (k * (n-k)! ) – so in this case 3! / (2 * (3-2)!) == 3! / (2*1) == 3!/2 == (3 * 2 * 1 ) == 3 * 1 == 3.
Sweet.
So, my real question – how many leaf nodes are there in a series? It’s not 7 factorial. Nor is it 7, taken two at a time (which would be 21, I think). It can’t be, because large parts of the random space of combinations aren’t possible – for example, given numbers 1 to 7, taken two at a time, you could draw 7 and 6, which isn’t a possible game score.
So I spent my time in the security line thinking about this problem, and my time on the plane writing about it, and no time actually doing the math. So, OtherEnders, this problem like so many others described in these pages, is left to you to solve. I can’t wait.
And no, this isn’t one of my interview questions.
Well, I’ve arrived in the Sunny Southwest. It’s warm here, and warmth is not conducive to math thinking in my head. So I'm out. I'm going to go ride a motorcycle, have a drink, and see my friend. I'll play my music too loud, and think peaceful thoughts. I will feel the Spirit from the Desert.
At the center, I hope you are well.
posted by Douglas at
3:55 PM
|
3 comments
