Timeline for Probabilty of two permutations having common elements?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 17, 2012 at 17:40 | vote | accept | jgonagle | ||
| Oct 17, 2012 at 17:40 | vote | accept | jgonagle | ||
| Oct 17, 2012 at 17:40 | |||||
| Jul 9, 2012 at 18:06 | comment | added | Anton Geraschenko | John McGonagle posted (as an answer, which I've moved to this comment): Yes, h^(-1) must necessarily span the group of permutations, so it stands to reason that so does the product. anyway, the rencontres numbers gave me the answer i was looking for. interesting to note that the limit only depends on the number of fixed points. thanks for the help! | |
| Jun 1, 2012 at 20:40 | answer | added | Patricia Hersh | timeline score: 6 | |
| May 18, 2012 at 0:31 | comment | added | Brendan McKay | @Igor: As $h$ ranges over all permutations, so does $gh$ for any fixed $g$. That's all that is needed to see it is obvious. | |
| May 17, 2012 at 16:29 | comment | added | Pietro Majer | A simpler, yet a bit schizoid way to put it. We may restate the problem in terms of two bijections $h$ and $g$ between two possibly different sets $X$ and $Y$, rather than permutations of a set $X$. Since they may be different, we may identify them through $h$, that is, we may assume that the map $h$ is the identity and $X=Y$. | |
| May 17, 2012 at 14:32 | comment | added | Igor Rivin | @Anthony: Yes, I know why it is true (though yours is a nice way of putting it), I was not sure how much background the OP had though... | |
| May 17, 2012 at 14:01 | comment | added | Anthony Quas | @Igor: it's pretty obvious: since Haar measure convolved with any delta measure is Haar measure, it follows that Haar measure convolved with Haar is Haar. | |
| May 17, 2012 at 13:40 | comment | added | Igor Rivin | It is not completely obvious that the product of two uniformly random permutations is uniformly random... | |
| May 17, 2012 at 12:28 | comment | added | jgonagle | thanks, that makes a lot of sense. wish i could give both of you some rep points | |
| May 17, 2012 at 11:28 | comment | added | Zsbán Ambrus | I agree with David Roberts: if g and h are independent uniform random permutations, then $ f := gh^-1 $ is also a uniform random permutation, and the number you want is just the number of fixpoints of that one permutation. So forget about g and h and just find the distribution of the number of fixed points of a single uniform random permutation f, which is a well-known problem. | |
| May 17, 2012 at 10:57 | comment | added | jgonagle | I have a heuristic algorithm that assigns nodes between two isomorphic graphs of size m. i want to find the chance that given a random assignment of nodes, that at least n of them will be correct. For the time being, im assuming the isomorphism is unique. I'd like to know so that I can compare the random case to my algorithm's performance. The problem statement seems simple enough (or maybe the exactly n correct assignments case) that I figured it might be a well known question. | |
| May 17, 2012 at 10:36 | comment | added | David Roberts♦ | You could also consider the permutation $h^{-1}g$, and see how many elements it fixes. What is your motivation for considering this problem? | |
| May 17, 2012 at 10:23 | history | asked | jgonagle | CC BY-SA 3.0 |