Rope, RoboRally, and Rice Residents
Feb. 4th, 2008 04:17 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyEr, I mean, no, I'm not Scooby Doo...
Let's go in backwards order. I remember Colin asking some time ago about how far back the pattern - or maybe he said "tradition" of Tufts House male president, female VP goes. "Twice is a tradition, three times is an ancient and honored tradition", eh? But I don't think this is really much of a pattern. This year we have Colin and Eve, last year we had Mark and Ginny, but the year before that, under Sean, we had a different vice president each quarter - first Jack, then Chris, then Mark. Of course, it's pretty unlikely we'll change the VP at all this year - the job has almost entirely disappeared. Someone (probably Laura, or maybe Bill or Dave) came up with the idea of making people sign up to bring food for house meeting weeks in advance, at the very first house meeting, and I don't think I've seen since first year a house meeting where we shouted at the VP for not doing his job. (Because, first year, that was really what he was there for. Not that we'd shout at Ginny.)
We played RoboRally again on Saturday; after the easy map last time, we tried one that turned out to be too hard. Or, the second flag was - lesson we quickly learned: harder flags should come later. And there should be a flag on the starting board. The result was that hardly anyone got a register locked all game. (Especially in combination with what we tried for options - that you get one for tagging a flag. Maybe next time we'll try the new edition rules for options, and just try to use boards with more accessible double-wrenches.) (Meanwhile, Noah is trying once again to organize a game of Diplomacy, now that Youlian has brought it - we'll see if that ever actually happens.)
Addendum 19:14: Also, here's something strange. Marissa was playing - I decided to go ahead and play anyway - and she didn't ruin the game! She wasn't a horrible sport! She did try to be nice to the other players (in-game), which suggests something wrong with her idea of it (she wasn't trying to bargain - could you play RoboRally diplomatically? - just being nice), and she was still annoying, but she didn't complain when she narrowly lost. And you know what, I think it's demonstrative of the more general fact that since the start of the year, Marissa has actually become largely tolerable! Still pretty annoying, but for her, this is a big step up.
So, the rope problem. This is another "Harry solves a math problem the stupid way" story (and a tale of many miscalculations). Youlian gives me the following problem, telling me there's a very simple solution: You've got n pieces of rope, and you randomly pair up the 2n ends, to get some number of loops of rope. What's the expected number of components?
First thing I did was try to get a handle on the space of possibiliites. Ways of making partitioning 2n elements into n pairs is (2n)!/2nn!, or 1⋅3⋅5⋅...⋅(2n-1). OK, so let's compute some small examples. 1 is obviously 1. 2, I can enumerate these, I get 4/3. 3... I don't know... well, I can tell how many there are with 3 or 1 components, so the number with 2 components is however many are left over. Oh, hah, I could have figured that out directly... anyway, I get 23/15. 4... I don't want to compute 4.
Do we have anything of a pattern? Nothing obvious. How about the differences? 4/3-1 is 1/3, obviously, and 23/15-4/3 is... well, in reality it's 1/5, but I don't remember what I computed it as. Had I got it right, I might have (on not much evidence, but correctly) conjectured that the sequence is 1+1/3+1/5+...+1/(2k-1), but I miscalculated, got some weird fraction, and figured I wasn't going to be getting it beforehand.
Now, Youlian insisted there was some very simple solution to this, and in fact Winston had already solved it, and he doesn't even do math. But whatever they were doing, I couldn't think of it. I wanted to count by decomposing into components, maybe get a recursion that way, but then you have to worry about just which ropes are in which... yeah, not going to get into that.
So I think: Well, this is an expected value problem, and what always do you do with expected value problems? Break it up! Thinking of Burnside's lemma, I thought, say we assign to each rope a value of 1 over the size of the component it's in, then these sum to give us the number of components. So I just have to compute the expected value of that and then multiply by n. But how to compute that? I then forget about the problem for a few days until Youlian reminds me.
I start again trying to find a simple solution, with no more luck. So... that expected value computation idea I had earlier... hey, I can compute that expected value! I can determine the probability that a given strand's component has size k! Because I consider just taking the strand and randomly tying others to it until I get a loop, and I can compute the probability that it takes k ties to do so. Oh, this will be nasty, to be sure, but that's how math is done, no? Use the nasty method to derive the answer, then once you have it, reverse-engineer a nice solution. So I do this, and I compute my epxected value (and multiply it by n) and get a result that contains this nasty sum, sum from k=1 to n of 4k(2(n-k) choose n-k)/k. And I think, hey, convolution! I'll just take its generating function! I mean I know the generating function of 1/k and hence 4^k/k, and of (2k choose k)...
Well, I then spend several days getting consistently wrong results because apparently I can't tell a k apart from a 1/k. I write down the generating function of 1/k as x/(1-x)², and don't think to question this for several days. I get a very nice closed-form result out of this, but it doesn't work at all. (OK, not quite consistent. Apparently there was a day where I forgot how exponents worked and thought the reciprocal of x^(5/2) was x^(2/5). But I caught that one pretty quickly.)
OK - time for some debugging. I've tested the nasty sum, so I didn't mess up before taking generating functions. I test what I get from the generating functions against my final result - they're the same. So my mistake must be somewhere in the middle. But I'm sure of all that as well...
Naturally I feel really stupid when I notice what I did. Unfortunately, log(1+x)/√(1+x) isn't nearly so nice as (1+x)^(-5/2) (this is after doing some substitution and ignoring some easy bits); in particular, I don't know how to get anything out of it, and it doesn't look like I'm going to be able to get some sort of property of the function that will give me a recursion from that. (And even if I do get a recursion, might I end up going in circles as I try to take its generating function to solve it? I decide to ignore that possibility until it comes up.) So, well, I differentiate. And I quickly see its first few derivatives are all of the same form, and I can easily come up with a recursion for the coefficients, and hence for the numerical derivatives themselves, and hence the numbers I want. After a lot of calculation and a number of errors, I finally conclude, a0=0, an+1=an+1/(2n+1).
...how the hell did I not noice that beforehand?! Because I can't calculate 23/15-4/3, apparently.
Well, I've proved it - now I just have to reverse-engineer a nice solution. (I mean, I don't have to, but...)
I think of a nice solution later that night, and not really at all inspired by my 1+1/3+1/5+... answer, either. Say Nk is the number of possibility with k strands, Ek is the expected value we want, and Tk is the total number of components, so Ek=Tk/Nk. Recall Nk=1⋅3⋅...⋅(2k-1). To compute Ek+1, consider any one strand. If it's in its own component, remove it. If it's not, contract it. As there are 2k ways to add a (k+1)th strand in an existing loop, we get Tk+1=2kTk+Tk+Nk=(2k+1)EkNk+Nk,
so Ek+1=Ek+1/(2k+1). And to make things even nicer, instead of computing Nk separately, we can use the same method to get Nk+1=Nk(2k+1).
Freakin' Method of Distinguished Element. All there was to it. And it's also pretty analogous to the proof of the recursion for the Stirling numbers. And somehow I ignored the most basic combinatorial technique. OK, not quite ignored it. I think I thought of picking out single strands, but didn't think seriously about it - i.e. only thought about single loops, and didn't think of contracting them.
Today Wai Lee tells me what the intended solution was. It's even nicer, though unlike my actual eventual nice solution, it doesn't have the property that it ought to have been bleedin' obvious. You start with n strands, and start tying them together. At each tie, either you tie a strand to itself, or make a loop, and have one less strand, or you tie two different strands together - in which case you can now just consider them as one strand, and so you have one less strand. Thus the expected value is the sum of the probabilities of making a loop at each step, each of which is easily seen to be 1/(2k-1), where k is the number of strands remaining. Pretty neat.
Fucking... distinguished element... wow. Well, I suppose 3 proofs are better than 2?
-Harry
Let's go in backwards order. I remember Colin asking some time ago about how far back the pattern - or maybe he said "tradition" of Tufts House male president, female VP goes. "Twice is a tradition, three times is an ancient and honored tradition", eh? But I don't think this is really much of a pattern. This year we have Colin and Eve, last year we had Mark and Ginny, but the year before that, under Sean, we had a different vice president each quarter - first Jack, then Chris, then Mark. Of course, it's pretty unlikely we'll change the VP at all this year - the job has almost entirely disappeared. Someone (probably Laura, or maybe Bill or Dave) came up with the idea of making people sign up to bring food for house meeting weeks in advance, at the very first house meeting, and I don't think I've seen since first year a house meeting where we shouted at the VP for not doing his job. (Because, first year, that was really what he was there for. Not that we'd shout at Ginny.)
We played RoboRally again on Saturday; after the easy map last time, we tried one that turned out to be too hard. Or, the second flag was - lesson we quickly learned: harder flags should come later. And there should be a flag on the starting board. The result was that hardly anyone got a register locked all game. (Especially in combination with what we tried for options - that you get one for tagging a flag. Maybe next time we'll try the new edition rules for options, and just try to use boards with more accessible double-wrenches.) (Meanwhile, Noah is trying once again to organize a game of Diplomacy, now that Youlian has brought it - we'll see if that ever actually happens.)
Addendum 19:14: Also, here's something strange. Marissa was playing - I decided to go ahead and play anyway - and she didn't ruin the game! She wasn't a horrible sport! She did try to be nice to the other players (in-game), which suggests something wrong with her idea of it (she wasn't trying to bargain - could you play RoboRally diplomatically? - just being nice), and she was still annoying, but she didn't complain when she narrowly lost. And you know what, I think it's demonstrative of the more general fact that since the start of the year, Marissa has actually become largely tolerable! Still pretty annoying, but for her, this is a big step up.
So, the rope problem. This is another "Harry solves a math problem the stupid way" story (and a tale of many miscalculations). Youlian gives me the following problem, telling me there's a very simple solution: You've got n pieces of rope, and you randomly pair up the 2n ends, to get some number of loops of rope. What's the expected number of components?
First thing I did was try to get a handle on the space of possibiliites. Ways of making partitioning 2n elements into n pairs is (2n)!/2nn!, or 1⋅3⋅5⋅...⋅(2n-1). OK, so let's compute some small examples. 1 is obviously 1. 2, I can enumerate these, I get 4/3. 3... I don't know... well, I can tell how many there are with 3 or 1 components, so the number with 2 components is however many are left over. Oh, hah, I could have figured that out directly... anyway, I get 23/15. 4... I don't want to compute 4.
Do we have anything of a pattern? Nothing obvious. How about the differences? 4/3-1 is 1/3, obviously, and 23/15-4/3 is... well, in reality it's 1/5, but I don't remember what I computed it as. Had I got it right, I might have (on not much evidence, but correctly) conjectured that the sequence is 1+1/3+1/5+...+1/(2k-1), but I miscalculated, got some weird fraction, and figured I wasn't going to be getting it beforehand.
Now, Youlian insisted there was some very simple solution to this, and in fact Winston had already solved it, and he doesn't even do math. But whatever they were doing, I couldn't think of it. I wanted to count by decomposing into components, maybe get a recursion that way, but then you have to worry about just which ropes are in which... yeah, not going to get into that.
So I think: Well, this is an expected value problem, and what always do you do with expected value problems? Break it up! Thinking of Burnside's lemma, I thought, say we assign to each rope a value of 1 over the size of the component it's in, then these sum to give us the number of components. So I just have to compute the expected value of that and then multiply by n. But how to compute that? I then forget about the problem for a few days until Youlian reminds me.
I start again trying to find a simple solution, with no more luck. So... that expected value computation idea I had earlier... hey, I can compute that expected value! I can determine the probability that a given strand's component has size k! Because I consider just taking the strand and randomly tying others to it until I get a loop, and I can compute the probability that it takes k ties to do so. Oh, this will be nasty, to be sure, but that's how math is done, no? Use the nasty method to derive the answer, then once you have it, reverse-engineer a nice solution. So I do this, and I compute my epxected value (and multiply it by n) and get a result that contains this nasty sum, sum from k=1 to n of 4k(2(n-k) choose n-k)/k. And I think, hey, convolution! I'll just take its generating function! I mean I know the generating function of 1/k and hence 4^k/k, and of (2k choose k)...
Well, I then spend several days getting consistently wrong results because apparently I can't tell a k apart from a 1/k. I write down the generating function of 1/k as x/(1-x)², and don't think to question this for several days. I get a very nice closed-form result out of this, but it doesn't work at all. (OK, not quite consistent. Apparently there was a day where I forgot how exponents worked and thought the reciprocal of x^(5/2) was x^(2/5). But I caught that one pretty quickly.)
OK - time for some debugging. I've tested the nasty sum, so I didn't mess up before taking generating functions. I test what I get from the generating functions against my final result - they're the same. So my mistake must be somewhere in the middle. But I'm sure of all that as well...
Naturally I feel really stupid when I notice what I did. Unfortunately, log(1+x)/√(1+x) isn't nearly so nice as (1+x)^(-5/2) (this is after doing some substitution and ignoring some easy bits); in particular, I don't know how to get anything out of it, and it doesn't look like I'm going to be able to get some sort of property of the function that will give me a recursion from that. (And even if I do get a recursion, might I end up going in circles as I try to take its generating function to solve it? I decide to ignore that possibility until it comes up.) So, well, I differentiate. And I quickly see its first few derivatives are all of the same form, and I can easily come up with a recursion for the coefficients, and hence for the numerical derivatives themselves, and hence the numbers I want. After a lot of calculation and a number of errors, I finally conclude, a0=0, an+1=an+1/(2n+1).
...how the hell did I not noice that beforehand?! Because I can't calculate 23/15-4/3, apparently.
Well, I've proved it - now I just have to reverse-engineer a nice solution. (I mean, I don't have to, but...)
I think of a nice solution later that night, and not really at all inspired by my 1+1/3+1/5+... answer, either. Say Nk is the number of possibility with k strands, Ek is the expected value we want, and Tk is the total number of components, so Ek=Tk/Nk. Recall Nk=1⋅3⋅...⋅(2k-1). To compute Ek+1, consider any one strand. If it's in its own component, remove it. If it's not, contract it. As there are 2k ways to add a (k+1)th strand in an existing loop, we get Tk+1=2kTk+Tk+Nk=(2k+1)EkNk+Nk,
so Ek+1=Ek+1/(2k+1). And to make things even nicer, instead of computing Nk separately, we can use the same method to get Nk+1=Nk(2k+1).
Freakin' Method of Distinguished Element. All there was to it. And it's also pretty analogous to the proof of the recursion for the Stirling numbers. And somehow I ignored the most basic combinatorial technique. OK, not quite ignored it. I think I thought of picking out single strands, but didn't think seriously about it - i.e. only thought about single loops, and didn't think of contracting them.
Today Wai Lee tells me what the intended solution was. It's even nicer, though unlike my actual eventual nice solution, it doesn't have the property that it ought to have been bleedin' obvious. You start with n strands, and start tying them together. At each tie, either you tie a strand to itself, or make a loop, and have one less strand, or you tie two different strands together - in which case you can now just consider them as one strand, and so you have one less strand. Thus the expected value is the sum of the probabilities of making a loop at each step, each of which is easily seen to be 1/(2k-1), where k is the number of strands remaining. Pretty neat.
Fucking... distinguished element... wow. Well, I suppose 3 proofs are better than 2?
-Harry
