/sci/ - Science & Math

>>3972742
Notes:
This question, like my previous, can be brought into the world of groups, namely symmetric groups. <span class="math">S_{1000}[/spoiler] contains all the possible permutations of the problem. So the question can be redefined as: given a random element of <span class="math">S_{1000}[/spoiler] what is the average cycle length?

I'm a slut. Pic related, it's me.

Background:
This actually happens every year to the frosh class at my school. However our school has singles and doubles and Triples. I want to try and solve the easy case, and see if I can use it's solution to help with the harder one. I'm going to try to make a python program to statistically get an answer, so we how average_cycle_length grows with n.

>>3972768
saved. you point?

so it's total number of solutions/2?
1000!/2

Ok, my first observation is that the overall average cycle length and the average "average cycle length" are different. Specifically, if you have n students and an average of c cycles, than the overall average cycle length is n/c. However, if you take the average in each specific instance and average those, you might get a different answer.

>>3972808
let me correct myself:
infinity because you can repeat rooms (duh). find the average of 1 to infinity...

>>3972818
Ok, the average cycle length wasn't that hard to find, the key is to look at just one person. It will take me a while to type up in latex though.

>>3972808
Why? Yes there are 1000! elements of <span class="math">S_{1000}[/spoiler]. But why a division by two

>>3972818
I'm trying to find the average of all such instances. In other words <span class="math"> \sum_{i=1}^{n!} \sum_{k=1}^{m} length of cycle_k[/spoiler]
where i is the i-th instance (there are n! of them in <span class="math">S_{1000}[/spoiler]) and k is the k-th cycle inside of a given i. (of which there are m of them)

>>3972825
>repeat rooms
You cannot. If person 1 is sent to room 1 again, the cycle is of length 1. Have you done anything with symmetric groups? the idea is as follows for <span class="math">S_{10}[/spoiler] for example, one element of the group is (123)(456)(7)(8)(9 10).
person 1 is sent to room 2, 2 to room 3, 3 to room 1... 7 is sent to his old room etc.

At t-1, only one iteration takes place. So at worse, we have the element (1 2 3 4 5 6 7 8 9 10) which creates a cycle of length 10.

>>3972836
Ok, so note that the average cycle length means the same thing as "the average length of a cycle that a specific guy is in".
The chance of a person being in a k-cycle is <span class="math">\frac{n-k+1}{n^2}[/spoiler] if I didn't make a mistake, but it shouldn't be hard to verify. Therefore, the average cycle length is
<span class="math">\mathbb{E}(k) = \sum_{k=1}^{n} k~\frac{n-k+1}{n^2}[/spoiler]

>>3972841
I'm sorry, I don't get what you mean by cycle. My logic was that I could take 1 turn to return to original (no change), or as much as n!. So you just take the average (which is actually (n1+1)/2)

>>3972869
see the post below that for clarification. The cycle at it's largest can contain n people.

>>3972868
But I guess thats for the overall average cycle length. I'll have to think a bit more to find what you are asking for. HOWEVER, as I mentioned earlier, that average that I calculated can be used to easily get the expected value for the number of cycles, so it solves half the problem.

>>3972868
wait shit, I made a mistake, its actually 1/n chance for each cycle length, so make it <span class="math">\mathbb{E}(k) = \sum_{k=1}^{n} \frac{k}{n} = [/spoiler], which is much simpler. Someone doublecheck for me please.

>>3972868
I cannot read latex unrendered. But I know if you look at all the m-cycles (cycle of length m for 1<=m<=n), There are n(n-1)...(n-m+1) / m such unique cycles possible

>>3972894
simplifying to <span class="math">\mathbb{E}(k) = \sum_{k=1}^{n} \frac{k}{n} = \frac{1}{n} \sum_{k=1}^{n} k = \frac{n(n+1)}{2n} = \frac{n+1}{2}[/spoiler] so the average number of cycles is <span class="math">\frac{2n}{n+1}[/spoiler]

>>3972898
Ok, I think I fucked up somewhere, but the basic idea is this:
given any random permutation, everyone has an equal chance to be moved to any given room. Therefore, the chance that anyone stays in place is 1/n.
The chance he moves somewhere else is (n-1)/n, and, given that, the chance that guy moves to his room is 1/(n-1), with n-1 in the denominator because that guys room has already been claimed by the original guy. It is clear that that simplifies to 1/n, and it simplifies similarly for any given permutation length.

>>3972903
Do you think you could explain some of this?
In your interpretation of the problem, we look at a specific student, then find on average per student what the length of their cycle is. Does your method into account that sum(cycle lengths) = n ?

>>3972918
I checked for n=2 and it doesn't work. I'm confident about that being the probability for a specific student, but the rest doesn't seem to work.

,aybe explain to us what the 3 cycles of n=5 are?

>>3972939
I think that's the right way to go about it for n very large. Sort of. But larger

>>3972946
n is the total number of students. In the one instance I gave the cycles are:
(1)
(2 4 5)
(3)
This makes up an element of the group <span class="math">S_5[/spoiler] (1)(2 4 5)(3)

Basically the idea behind these elements is that they determine a permutation. This particular permutation sends 1 to itself, sends 2 to 4, 4 to 5, 5 to 2, and 3 to itself.

(2 4 5) would be considered a cycle of length 3, because it has 3 elements in it

>>3972979
oops didn't finish that though. You can use probability that way for large groups of people, as one persons assignment won't effect the rest of the population that much. But the probabilities are not independent at all

>>3972988
true, but often independent probabilities are useful for calculating more general facts. Its been too long since I've taken probability though

>>3973003
OK, I don't have the solid math yet, but it seems like overall it ends up being sum(1/k) for the average number of cycles. It works for n up to 3