Another test of the platform.
A group of men and women are randomly arranged in a line. What is the expected number of men who have a woman next them? How would this change if they were arranged in a circle instead of a line?
Let denote a sequence of Bernoulli random variables where . The total number of permutations of the people is . The number of permutation with a man in position is , where the binomial coefficient gives the number of ways to select a man to occupy the position and the second factor is the number of ways to permute the remaining people. Hence, under the assumption of equally likely outcomes, A new sequence of Bernoulli random variables is introduced where . A man in position 1 will only have a woman next to him if the person in position 2 is a woman; a man in position will only have a woman next to him if the person in position is à woman; and a man in position will have woman next to him if the person in position or position is a woman. Consequently Clearly, is the total number of men with at least one woman next to them. The linearity of expectation gives or, after a substitution from , Equally likely outcomes gives and Therefore
Let’s turn to how this expectation changes if the people are permuted on a circle. The primary difference between permutations on a line and permutations on circle is that on the line the positions are distinguishable by their location relative to one of the ends, for example from the left most position, and this does not depend on the choice of the origin on the line1,however, on the circle, the positions are indistinguishable absent a choice of a set of coordinate axes.
Suppose that one sets up coordinate axes and measures angles counterclockwise relative to the axis. The position on the circle relative to the coordinate system is placed at . With this arbitrary choice of a coordinate system, the permutation of people on the circle reduces to the permuting people on the line. However, if the coordinate system is rotated by an angle counterclockwise, the positions are relabeled as follows This change of coordinate system does not change the circular permutation, but it corresponds to a distinct linear permutation. The upshot is that there are distinct linear permutations which map to the same circular permutation. Since there are linear permutation, there are circular ones.
A second difference between linear and circular permutations, and the one most important for consideration here, is the nearest neighbor structure. On the line, the positions and are nearest neighbors if and only if . On the circle, the positions and , relative to some coordinate system, are nearest neighbors if and only if 2. For , the nearest neighbors on the circle are the same as the nearest neighbors on the corresponding line. The difference is the positions and on the circle are nearest neighbors, but the those positions on the line are not.
To answer the question of how the expected number of men with at least one woman neighbor changes when the permutations are on a circle, select a coordinate system for the circle and consider the corresponding linear permutation with positions 1 and treated as nearest neighbors.
Let be a sequence of Bernoulli random variable defined by . With the modified neighborhood structure, Again is the total number of men with at least one woman next to them. The linearity of expectation gives The linearity of expectations and equally likely outcomes gives . Observe that the expectations in do not depend on . Consequently these expectation are independent of the coordinate system selected at the onset. Hence is the expected number of men with at least one woman neighbor when men and women are permuted on a circle.