tag:blogger.com,1999:blog-264226589944705290.post7948594752895080347..comments2024-09-25T08:51:01.854-07:00Comments on God Plays Dice: How many fixed points do involutions have?Michael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-264226589944705290.post-10902956833121297522010-03-18T18:04:50.513-07:002010-03-18T18:04:50.513-07:00Hey,
I am regular visitor of this website[url=htt...Hey,<br /><br />I am regular visitor of this website[url=http://www.weightrapidloss.com/lose-10-pounds-in-2-weeks-quick-weight-loss-tips].[/url]Plenty of useful information on godplaysdice.blogspot.com. Do you pay attention towards your health?. Let me present you with one fact here. Recent Scientific Research points that closely 80% of all U.S. grownups are either fat or weighty[url=http://www.weightrapidloss.com/lose-10-pounds-in-2-weeks-quick-weight-loss-tips].[/url] Hence if you're one of these individuals, you're not alone. Infact many among us need to lose 10 to 20 lbs once in a while to get sexy and perfect six pack abs. Now next question is how you can achive quick weight loss? You can easily lose with with little effort. If you improve some of your daily diet habbits then, its like piece of cake to quickly lose weight.<br /><br />About me: I am webmaster of [url=http://www.weightrapidloss.com/lose-10-pounds-in-2-weeks-quick-weight-loss-tips]Quick weight loss tips[/url]. I am also health expert who can help you lose weight quickly. If you do not want to go under painful training program than you may also try [url=http://www.weightrapidloss.com/acai-berry-for-quick-weight-loss]Acai Berry[/url] or [url=http://www.weightrapidloss.com/colon-cleanse-for-weight-loss]Colon Cleansing[/url] for fast weight loss.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-34393658990954552452010-01-31T18:18:56.699-08:002010-01-31T18:18:56.699-08:00Good brief and this enter helped me alot in my col...Good brief and this enter helped me alot in my college assignement. Gratefulness you seeking your information.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-73781159566327467602010-01-22T23:42:04.890-08:002010-01-22T23:42:04.890-08:00Keep on posting such themes. I love to read blogs ...Keep on posting such themes. I love to read blogs like this. BTW add more pics :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-82762787261792122332009-11-22T06:57:14.200-08:002009-11-22T06:57:14.200-08:00It was rather interesting for me to read the blog....It was rather interesting for me to read the blog. Thank author for it. I like such topics and anything that is connected to this matter. I definitely want to read more soon.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-3737664011788056682008-02-05T13:41:00.000-08:002008-02-05T13:41:00.000-08:00David,The Poisson distribution tends to a normal d...David,<BR/>The Poisson distribution tends to a normal distribution (after proper normalization) as the parameter tends to infinity, so you and Isabel are at a complete agreement.<BR/>All that is left is to indeed prove that it's Poisson. I haven't thought about it, but my guess is that it shouldn't be too hard.Ori Gurel-Gurevichhttps://www.blogger.com/profile/03570318768726906432noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-88028526738869415132008-02-05T10:55:00.000-08:002008-02-05T10:55:00.000-08:00Check out this histogram depicting the probabiliti...Check out <BR/><A HREF="http://www-math.mit.edu/~speyer/Involutions4096.PNG" REL="nofollow">this histogram</A> <BR/>depicting the probabilities of various numbers of fixed points in a random involution of 4096 elements.<BR/><BR/>David S.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-53154157373706862582008-02-05T10:50:00.000-08:002008-02-05T10:50:00.000-08:00Oh, you're right, I'm dumb :). The data below is v...Oh, you're right, I'm dumb :). The data below is variances, not standard deviations. So the standard deviations are n^{1/4}, even though the bell curves look much wider by eye. <BR/><BR/>OK, now I think we are saying the same thing. Mean=n^{1/2}, Std. Dev. = n^{1/4}. The only thing we disagree on is that I think we are looking at a normal distribution and you think it is Poisson. Let me put up a picture and see if I convince you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-31787494260574681122008-02-05T10:45:00.000-08:002008-02-05T10:45:00.000-08:00OK, some numerical data. When n=1024, 2500, 3025, ...OK, some numerical data. <BR/><BR/>When n=1024, 2500, 3025, 4096<BR/><BR/>the mean of k is<BR/>31.5116, 49.5074, 54.5068, 63.5058<BR/><BR/>and the std. dev is<BR/>31.0193, 49.0124, 54.0113, 63.0097<BR/><BR/>That's a great fit for a standard deviation of n^{1/2}. But all the pictures look like bell curves! What the heck?<BR/><BR/>David SpeyerAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-68964502703625696672008-02-05T10:41:00.000-08:002008-02-05T10:41:00.000-08:00David,the standard deviation can't be n^{1/2}, of ...David,<BR/><BR/>the standard deviation can't be n^{1/2}, of course -- that would mean that none of the mass of the distribution is more than one standard deviation below the mean. The only distributions like that, if I remember correctly, are distributions with all the mass at two points; certainly a normal distribution (which I suspected this is even without seeing your data, because that's just how a lot of these things work) won't be of that sort.<BR/><BR/>But the <I>variance</I> (the square of the standard deviation) could be n^{1/2}, as I conjectured in the original post, making the standard deviation n^{1/4}. Then we would have from the non-negativity of the number of fixed points that none of the mass of the distribution is more than n^{1/4} standard deviations below the mean, which is a reasonable thing to say since the result is true in some asymptotic sense as n goes to infinity.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-33283234465507223152008-02-05T10:33:00.000-08:002008-02-05T10:33:00.000-08:00OK, I've got some data now and it is -- inconclusi...OK, I've got some data now and it is -- inconclusive. I can do values of n around 1000 in basically no time; the largest that I have done is 4096.<BR/><BR/>It is definitely true that the distribution is peaked almost exactly at n^{1/2}. It also looks like a bell curve. I haven't got the code somputing standard deviations yet, but visually it looks like n^{1/2}. So this sounds kind of like a bell curve with center and variation n^{1/2}. But that is impossible. We know that the probability is precisely zero of having a negative number of fixed points. <BR/><BR/>I'll probably put some pictures and data up online once I clean it up.<BR/><BR/>David Speyer`Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-40853715895765007132008-02-04T23:26:00.000-08:002008-02-04T23:26:00.000-08:00Here's one intuitive reason why conditioning on be...Here's one intuitive reason why conditioning on being an involution gives so many more 2-cycles (which may also be able to made rigorous into an n^(1/2) proof):<BR/><BR/>Let us generate our random involution as follows. <BR/><BR/>1. Generate a permutation sigma uniformly at random.<BR/><BR/>2. Expose the cycle containing n. If that cycle has length 3 or more, give up and start again from the step 1. <BR/><BR/>3. Otherwise, expose the rest of the cycles. If you have an involution, keep sigma. Otherwise, go back to step 1.<BR/><BR/>After step 2, we're equally likely to have placed n in a 2 cycle as in a 1 cycle. However, we still need to pass step 3. <BR/><BR/>If n is in a cycle of length 1, we keep sigma in this final step as often as a random permutation on n-1 elements is an involution. If n is in a cycle of length 2, we keep sigma as often as a random permutation on n-2 elements is an involution. <BR/><BR/>Involutions become significantly more rare as n increases, so a permutation on n-2 elements is much more likely to be an involution than one on n-1 points. Correspondingly, we keep many more of the permutations with n in a 2 cycle than with n in a 1 cycle.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-64171735704254392652008-02-04T13:20:00.000-08:002008-02-04T13:20:00.000-08:00David,I don't see an obvious flaw there. But I tr...David,<BR/><BR/>I don't see an obvious flaw there. But I trust my data for now. (And it's pretty easy to generate -- just the second moment can similarly be obtained by differentiation. The exact asymptotic expansion is hard to get, of course, but coefficients of z^n in exp(z+z^2/2) arbitrarily far out are easy to find. Then again, your argument for o(n^{1/2}) variance could be correct with variance something like n^{1/2}/(log log n) which would be hard to detect when I've only calculated the first hundred or so coefficients of the generating function. At some point I'm going to actually do the computations I alluded to and write this and various other results of the same type up more formally; keep an eye out here. Thanks for your comment!Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-74254628906984558502008-02-04T12:49:00.000-08:002008-02-04T12:49:00.000-08:00I think that I don't believe your claim about the ...I think that I don't believe your claim about the variance. I haven't been completely rigorous, but I think the variance should be of order n^{1/4}, not n^{1/2}. <BR/><BR/>Rough argument for why it should be less than n^{1/2}: First, correct the ratio computation above. In fact, r_{k,n}:=a_{k,n}/a_{k-1,n}=(n-k+2)/k(k-1). (This isn't important, but I'd be embarassed to keep carrying this error around.) Fix any constant c>0. I claim that, if k>(1+c)*n^{1/2} then a_{k,n}/a^{n^{1/2},n} decays rapidly in n. More precisely, a_{k,n}/a^{n^{1/2},n} is a product of about c n^{1/2}/2 terms of the form r_{j,n}, at least c n^{1/2}/4 of which are less than O(n/(1+c/2)^2 n). So a_{k,n}/a^{n^{1/2},n}=O((1+c/2)^{- c/2 n^{1/2}}). In particular, this decays faster than the reciprocal of any polynomial, so terms with this large k will, as n goes to infinity, contribute nothing to the variance (or, more generally, to any moment.) The same argument shows that there is no contribution from k<(1-c)n^{1/2}. In other words, in the limit probability distribution, everything is clumped around n^{1/2}, with a variance that is o(n^{1/2}).<BR/><BR/>I have a more precise argument, explaining why I believe the variance should by n^{1/4}, but I am worried that I have made some dumb error. Does what I have done make sense so far? How good is your data?<BR/><BR/>David SpeyerAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-17564187722907044232008-02-04T11:52:00.000-08:002008-02-04T11:52:00.000-08:00Here is a simple argument that we should expect a ...Here is a simple argument that we should expect a random involution of n points to have about n^{1/2} fixed points:<BR/><BR/>Recall (or prove) that the number of fixed point free involutions of 2n elements is <BR/>(2n-1)(2n-3)(2n-5)...5*3*1. So the number of involutions of an n element set which have k fixed points is<BR/><BR/>a_{k,n}=(n choose k) *(n-k-1)(n-k-3)(n-k-5)...5*3*1<BR/>=n*(n-1)*(n-2)*...*(n-k+2)*(n-k+1)<BR/>*(n-k-1)*(n-k-3)*...*5*3*1/k!<BR/><BR/>where k must have the same parity as n. Then a_{k,n}/a_{k-1,n}=(n-k)/k(k-1)<BR/><BR/>So a_{k,n} increases with k as long as (n-k)>k(k-1) and decreases with k thereafter. Rearranging n-k > k(k-1), we get n>k^2.<BR/><BR/>We should be able to use Stirling's formula to work out the limiting distribution of the number of fixed points.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-41675606505835724462008-02-03T21:47:00.000-08:002008-02-03T21:47:00.000-08:00It just seems that there's some similarity, in tha...It just seems that there's <I>some</I> similarity, in that you're looking for pairs which satisfy some condition together.John Armstronghttps://www.blogger.com/profile/15177732626660057584noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-14570770006751542382008-02-03T16:55:00.000-08:002008-02-03T16:55:00.000-08:00John,not as far as I know. But I don't have any r...John,<BR/><BR/>not as far as I know. But I don't have any reasonable explanation for why it should be true yet, other than that that's what the generating functions say. I'm looking for one.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-39084567669787709572008-02-03T13:25:00.000-08:002008-02-03T13:25:00.000-08:00Random thought: is there a relationship between th...Random thought: is there a relationship between the n^{1/2} that shows up here and that which shows up in the "birthday paradox"?John Armstronghttps://www.blogger.com/profile/15177732626660057584noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-52865126039719051232008-02-03T11:20:00.000-08:002008-02-03T11:20:00.000-08:00Jack,thanks. That's basically what I wanted to sa...Jack,<BR/><BR/>thanks. That's basically what I wanted to say, although for some reason words failed me yesterday.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-21289613037667331252008-02-03T09:04:00.000-08:002008-02-03T09:04:00.000-08:00"a_(n-1) / a_n is the probability that any given e..."a_(n-1) / a_n is the probability that any given element of an involution is actually a fixed point -- although it's hard to say exactly why this should be true"<BR/><BR/>Given one of the a_n involutions on [n], choose an element and ask "is this a fixed point?" Surely by symmetry it doesn't matter which point we choose--they all have the same probability of being a fixed point, so choose the last one, n.<BR/><BR/>It is a fixed point iff the rest of the permutation, which is a permutation on [n-1], is an involution in its own right. Well, this happens a_(n-1) times out of the a_n, hence the probability a_(n-1) / a_n.I. J. Kennedyhttps://www.blogger.com/profile/04805435564360543720noreply@blogger.com