No copying, "infinite" students

Probability Level 3

$n$ students are arranged in a line such that each student is sitting next to their good friends, and each student has no other good friends other than the students they are sitting next to.

If a teacher randomly reallocates their seats, what is the probability $P_n$ that none of these $n$ students sit next to their good friends?

Submit your answer as the limit $\displaystyle \lim_{n\to\infty} P_n.$

Inspiration

The answer is 0.1353.

3 solutions

Alexander Schierbeck-Hansen
Dec 17, 2018

The probability that a given student (not the first or last in the line) sits next to none of their friends, is number of non-friends divided by total number of students: $p = \frac{n - 2}{n} = 1 - \frac{2}{n}$ We want to pick each student in the line, and see how probable it is for them to sit next to a non-friend. For a near infinitely large number of students $n$ , we may ignore terms to the probability that arise from sampling the students without replacement. Therefore we may assume the probabilities of each student sitting next to a non-friend are independent, thus $P_n = p^n$ . Hence: $\lim_{n\rightarrow \infty}P_n = \lim_{n\rightarrow \infty}p^n = \lim_{n\rightarrow \infty} (1 - 2/n)^n = \exp(-2) \approx 0.1353$ In the equation above the identity $\lim_{n\rightarrow \infty} (1 + a/n)^n = \exp(a)$ is used.

I think that the probability for a givent student to sits next to none of their friends is number of non-adjacent to friends places divided by total of possibles places. So if we place the 2 friends first, which both have 2 adjacents seat when n goes infinite, we should end up with $p = \frac{n - 4}{n - 2}$ . And it turns out that I obtain the same result as you with this formula ! So both were correct ! Interesting ! :D

Ekalawen Illfasidrel - 2 years, 5 months ago

Let the student be X and the 2 friends be A and B. Your probability ignores the fringe cases that A is next to or one away from B. Assuming seat n is next to seat 1 (Basically ignoring end seats and treating all seats the same), and ignoring errors from sampling with replacement as before:

P(A is next to B) = $\frac{2}{n-1}$ P(X is NOT next to A or B | A is next to B) = $\frac{n-4}{n-2}$

P(A is one away from B) = $\frac{2}{n-1}$ P(X is NOT next to A or B | A is one away from B) = $\frac{n-5}{n-2}$

Otherwise P(X is NOT next to A or B) = $\frac{n-6}{n-2}$

Adding these together: $\frac{2}{n-1} \frac{n-4}{n-2} + \frac{2}{n-1} \frac{n-5}{n-2} + \frac{n-5}{n-1} \frac{n-6}{n-2} = \frac{n^2-7n+12}{(n-1)(n-2)} = 1 - \frac{4n-10}{n^2-3n+2}$

This can be worked out simply by placing A and B after X, with probability $\frac{n-3}{n-1} \frac{n-4}{n-2}$ . But this involves placing 2 students for every initial 1. So we must take $lim_{n\to\infty} (1 - \frac{4n-10}{n^2-3n+2})^\frac{n}{2}$ = $lim_{k\to\infty} (1 - \frac{2}{k})^k$ .

A different way to tackle the problem would be to look at the student to the right of a given one, (If no one is to the right of their friends, no one can be to the left of their friends [assuming seat n is next to seat 1 as n tends to infinity] ):

Assuming Seat n is next to seat 1 again:

P(X is not to the right of A) = $\frac{n-3}{n-1}$

Hence, P(No one is next to their friends) = $(\frac{n-3}{n-1})^n$ = $(1-\frac{2}{n-1})^n$ .

Alex Burgess - 2 years, 5 months ago

But $1-\frac {4n+10}{n^2-3n+2}$ is negative for $n$ in the interval (1,8). Are you sure this is correct?

Parth Sankhe - 2 years, 5 months ago

@Parth Sankhe – Apologies, should be $4n-10$ . Equal to $\frac{n-3}{n-1} \frac{n-4}{n-2}$ .

Alex Burgess - 2 years, 5 months ago

Yes, exactly. BTW, this relationship between (1-p)^n and exp(-pn) is used very often in probabilistic methods.

Richard Desper - 2 years, 5 months ago

Let the student be X and the 2 friends be A and B. Assuming seat n is next to seat 1 (Basically ignoring end seats and treating all seats the same), and ignoring errors from sampling with replacement as before:

P(A is next to B) = $\frac{2}{n-1}$ P(X is NOT next to A or B | A is next to B) = $\frac{n-4}{n-2}$

P(A is one away from B) = $\frac{2}{n-1}$ P(X is NOT next to A or B | A is one away from B) = $\frac{n-5}{n-2}$

Otherwise P(X is NOT next to A or B) = $\frac{n-6}{n-2}$

Adding these together: $\frac{2}{n-1} \frac{n-4}{n-2} + \frac{2}{n-1} \frac{n-5}{n-2} + \frac{n-5}{n-1} \frac{n-6}{n-2} = \frac{n^2-7n+12}{(n-1)(n-2)} = 1 - \frac{4n-10}{n^2-3n+2}$

Assuming Seat n is next to seat 1 again:

P(X is not to the right of A) = $\frac{n-3}{n-1}$

Hence, P(No one is next to their friends) = $(\frac{n-3}{n-1})^n$ = $(1-\frac{2}{n-1})^n$ .

Alex Burgess - 2 years, 5 months ago

Nicola Mignoni
Dec 20, 2018

Let's define the random variable $X_i$ such that

$\displaystyle X_i = \begin{cases} 1, & \mbox{if } i\mbox{ is is sitting next to their good friends} \\ 0, & \mbox{otherwise } \end{cases}$

Notice that, since the students are arranged in a line, student $1$ and student $n$ have just one good friend. Hence,

$\displaystyle \mathbb{P}(X_1=0)=\mathbb{P}(X_n=0)=\frac{n-2}{n-1}$

while

$\displaystyle \mathbb{P}(X_k=0)=\Big(\frac{n-2}{n-1}\Big)^2, \hspace{5pt} 2 \leq k \leq n-1$

The number of student sitting next to their good friends is $\displaystyle N=\sum_{i=1}^{n} X_i$ . So,

$\displaystyle P_n=\mathbb{P}(N=0)=\mathbb{P}(X_1=0 \cap X_2=0 \cap \dots \cap X_n=0)= \Big(\frac{n-2}{n-1}\Big)^2 \Bigg[\Big(\frac{n-2}{n-1}\Big)^2\Bigg]^{(n-2)}=\Big(\frac{n-2}{n-1}\Big)^{2(n-1)}$

Eventually

$\displaystyle \lim_{n \to \infty} P_n=\lim_{n \to \infty} \Big(\frac{n-2}{n-1}\Big)^{2(n-1)}=\Big(1-\frac{1}{n-1}\Big)^{2(n-1)}=\frac{1}{e^2}\approx \boxed{0.1353}$

$P(X_1=0) = P(X_1 \text{is placed on the edge again}) \frac{n-2}{n-1} + P(X_1 \text{is not placed on the edge again}) (\frac{n-2}{n-1})^2 = \frac{2(n-2)}{n(n-1)} + \frac{(n-2)^2(n-3)}{n(n-1)(n-2)}=\frac{n-2}{n}$

Similarly,

$P(X_k=0)=\frac{2(n-3}{n(n-1)} + \frac{(n-2)(n-3)(n-4)}{n(n-1)(n-2)}=\frac{(n-2)(n-3)}{n(n-1)}$

Alex Burgess - 2 years, 5 months ago

Yeah. Agree.

远航王 - 2 years, 5 months ago

Why does everybody here seems to asume that the X_{i} are stochastically independent? I dont think this is generally true with finite n.

mopcku77 Biki - 2 years, 5 months ago

Agreed. Not sure how to upvote this comment

Thomas J - 2 years, 5 months ago

The events $X_i$ are not independent for any finite $n$ , but, in the limit as n goes to infinity, cross terms between different $X_i$ become negligible.

If you instead look a circle of $A_i$ instead, such that $A_1$ is next to $A_n$ , and define $Y_i = 1$ if $A_i$ is to the right of a good friend, and $0$ otherwise.

For $a$ and $b$ greater than 3 apart, $P(Y_a = 0 ) = P(Y_b = 0 ) = \frac{n-3}{n-1}$ and $P(Y_a = 0, Y_b = 0 ) = \frac{n^2-7n+14}{(n-1)(n-2)} = (\frac{n-3}{n-1})^2 +\frac{4}{(n-1)^2(n-2)}$ .

Similarly, for $a$ next to $b$ , $P(Y_a = 0, Y_b = 0 ) = (\frac{n-3}{n-1})^2 -\frac{n-5}{(n-1)^2(n-2)}$ .

These examples are both asymptotic to $(\frac{n-3}{n-1})^2$ as $n$ goes to infinity.

The approximation that the people sit in a circle as apposed to a straight line can be made at this limit.

Alex Burgess - 2 years, 5 months ago

Agreed. All these solutions are wrong. I manually computed pn for n=4,5,6. If you write pn=an/n! Then a4 = 2 a5 = 14 a6 = 90

Luca Di Fazio - 1 year, 4 months ago

Laurent Shorts
Dec 17, 2018

Sequence number A002464 at OEIS is “number of permutations of length $n$ without rising or falling successions”.

The probability $P_n$ is $\dfrac{a(n)}{n!}$ , as there is $n!$ possible permutations.

On OEIS, it's written that the sequence has asymptotic $\dfrac{a(n)}{n!} \sim \dfrac{(1 - \frac2{n^2} - \frac{10}{3n^3} - \frac6{n^4} - \frac{154}{15n^5})}{e^2}$ .

(I'll write my solution here, since it seems that I cannot add my own solution...) I worked out the exact probability, and my result corresponds to the formula by Max Alekseyev for A002464 .

Let $S_1, \ldots, S_n$ be the students, and let $T_i$ be the event that $S_i$ sits next to $S_{i+1}$ . By the inclusion-exclusion principle we have $P_n = 1 + \sum_{k=1}^{n-1} \sum_{\stackrel{A\subseteq\{1,\ldots,n-1\},}{|A|=k}} (-1)^k P\left(\bigcap_{i\in A}T_i \right)$ Each chain of consecutive integers in $A$ forms a group of students, who must sit together in order, or in reverse order. Call the number of groups $g$ . E.g. if $A=\{1,2,4\}$ , then we have two groups: $(S_1,S_2,S_3)$ and $(S_4,S_5)$ , so $k=3$ and $g=2$ . Note that $1 \le g \le \min(k,n-k)$ always.

For a given $A$ , there are $g$ groups and $n - k - g$ single students, giving $(n-k)_g$ ways to place the groups, where $(n)_m$ is the falling factorial. Each group has two possible orderings (ascending and descending), and there are $(n)_{k+g}$ ways in total to place the $k+g$ grouped students on the $n$ seats. We get: $P\left(\bigcap_{i\in A}T_i \right) = \frac{(n-k)_g \cdot 2^g}{(n)_{k+g}} = \frac{2^g}{(n)_{k}}$

Now lets count the number of sets $A$ with $k$ elements and $g$ chains of consecutive numbers. We might classify the sets into chain-types. E.g. our example set $A=\{1,2,4\}$ has chain-type $(**,*)$ or $(2,1)$ , since there is one chain of length 2 and one chain of length 1, in that order. There are $k$ elements to be distributed into $g$ distinct, non-empty chains, giving $\binom{k-1}{g-1}$ chain-types by "stars and bars".

How many sets have a given chain-type? We consider the $g$ chains as bars in another "stars and bars"-argument. All but the last chain must be followed by an element not in $A$ , so we get $(n-1)-(k+g-1) = n-k-g$ "stars", which gives $\binom{n-k}{g}$ sets.

Putting it all together: $P_n = 1 + \sum_{k=1}^{n-1} \frac{(-1)^k}{(n)_{k}} \sum_{g=1}^{\min(k,n-k)} \binom{k-1}{g-1} \binom{n-k}{g} 2^g$

EDIT: I haven't worked it out, but we also want to show that the above converges to $e^{-2}$ for $n \to \infty$ . Notice that the expression can be written as: $P_n = 1 + \sum_{k=1}^{n-1} \frac{(-1)^k}{k!} \sum_{g=1}^{\min(k,n-k)} \frac{\binom{k-1}{g-1} \binom{n-k}{g}}{\binom{n}{k}} 2^g$ The fraction with the binomial coefficients seems to converge to 1 for $g=k$ and to 0 otherwise, and the inner sum converges to $2^k$ , which nicely gives the Taylor series for $e^{-2}$ . With some work, I suppose this could be made rigourous.

Malte Juhl - 2 years, 5 months ago

No copying, "infinite" students

The answer is 0.1353.

3 solutions

0 pending reports