Random seat assignments probability/algorithms question

Question

Suppose there are $M$ seats and $N \leq M/2$ people for those seats.

The seats are assigned as follows:

Each person generates uniformly a random permutation of the $M$ seats. When it is their turn they will pick the first seat in their permutation that is not occupied.

There are a couple of questions associated with this:

(a) First we want to see that the probability that any of the people will have to check more than $k$ seats before they find an empty seat according to their permutation is at most $2^{-k}$

(b) Then see the probability of not finding a new seat within the first $2 \log_2 N$ checks is at most $1/N^2$

(c) Let $S$ be the maximum number of checks that any person had to make. We want to see that $\mathbb{E}[S] = O(\log N)$

One can see this as follows:

The worst case scenario is when $k = N = M/2$ since this is when things are most "full".

In this case the first $k$ seats are taken implies that they appear in the previous members permutations in their first $k = N/2$ seats.

So the probability of the $i$th seat being taken $i < k$ is the probability that a previous person's permutation had the $i$th seat in their first half. Since exactly half of the total number of permutations feature the $i$th seat appearing in the first half of the sequence, we see that the probability of the $i$th seat being taken is $1/2$.

Do this for each of the $k$ seats to get a total probability of at most $2^{-k}$

I think this is right albeit I didn't explain it very well.

(b) is just a matter of substituting in (a)

(c) is where I'm stuck. Would appreciate some help!

Answer 1

The event that $S$ is greater than $k$ is the union of the events that some person required more than $k$ checks. Using the union bound, together with your result from part (a),

\begin{align} P(S>k) &\le N2^{-k}. \end{align}

You then have that $$ \begin{align} P(S>\phantom{0+\,}\log_2 N)&\le N2^{-\log_2 N}=1,\\ P(S>1+\log_2 N)&\le 2^{-1},\\ P(S>2+\log_2 N)&\le 2^{-2},\\ \vdots\\ P(S>j+\log_2 N) &\le 2^{-j},\\ \vdots \end{align} $$ and so on. This easily implies that $E[S]\le \lceil\log_2 N\rceil +1$, using for the formula $E[S]=\sum_{k=0}^\infty P(S>k)$. Indeed, the first $\lceil \log N \rceil$ terms in the infinite sum $\sum_{k=0}^\infty P(S>k)$ are each bounded above by $1$, and the larger terms are bounded above by a geometric series summing to $1$.