Problem: n chairs are arranged in a circle, and n people are being seated on them randomly as they arrive. we number them $a_1, .., a_n$, according to the order they arrive by.
We define the event $A_i$ that person $a_i$ and $a_{i+1}$ sit next to each-other.
Calculate the probability that such an i exists, or an upper bound if exact calculation isn't possible.
In other words, we need to calculate the probability that:
$\exists i, 1\le i \le n-1: a_{i}$ and $a_{i+1}$ sit next to each-other
and I think it would be:
$Pr[\cup_{i=1}^{n}A_i]=\sum_{i=1}^{n}Pr[A_i]-\sum_{i<j}Pr[A_i\cap A_j]+...+{(-1)}^{n+1}Pr[\cap_{i=1}^{n}A_i]$
First, the probability that any i, j sit next to each other is:
$Pr[A_i]=\frac{2(n-2)!}{(n-1)!}=\frac{2}{(n-1)}$
The other Pr[..]'s were complicated to calculate since it differs if j=i+1 or j>i+1, and so on for each iterator we add for other sums, and I couldn't conclude any formula for them all.
How can I calculate/approximate this $Pr[\cup_{i=1}^{n}A_i]$ ?
edit: A friend's suggested solution
In a group of n people, we have $n\choose2$ pairs, and to choose a pair of two consecutive people in a circle we have $n-1$ options. Thus the probability to choose such a pair is $\frac{n-1}{n\choose2}$. For each pair, the probability that they sit next to each other is $\frac{2}{n-1}$. So, the probability that an i exists is:
$Pr[\cup_{i=1}^{n-1}{S_i}]\le \Sigma_{i=1}^{n-1}{S_i}=\Sigma_{i=1}^{n-1}{\frac{n-1}{n\choose2}\frac{2}{n-1}}=\Sigma_{i=1}^{n-1}{\frac{2}{n\choose2}}=(n-1)\cdot2/{{\frac{n!}{2!(n-2)!}}}=(n-1)\cdot2/{\frac{n(n-1)}{2!}}=(n-1)\frac{2}{\frac{n(n-1)}{2!}}=(n-1)\frac{4}{n(n-1)}=\frac{4}{n}.$
(While I agree with the union and the sum... I don't agree with the need to choose a pair. The probability that a pair exists $\equiv$ the probability that at least 1 pair sit next each other....)