
> 
> **Q.** Let $G = (V, E)$ be a graph with $V = \{v\_1, \cdots, v\_n\}$ and $E = \{(v\_i, v\_{i+1}) \mid 1 \leq i < n\}$. If we repeatedly remove vertices from $G$ uniformly randomly until the set of vertices $V'$ remained constitute an independent set of the original $G$ (i.e., $\forall u, v \in V'$, $(u, v)\notin E$), what is the expected size of the independent set $V'$?
> 
> 
> 



Expected Size of Independent Set
[Previous answer was completely wrong.]


Denote by $p\_k$ the probability that at least $k$ vertices remain. Then the expectation is of course $\sum p\_i$. I claim that $p\_k=\frac{(n-k+1)! (n-k)!}{(n-2k+1)! n!}$, it is about $e^{-k^2/n}$ and thus the asymptotics is the same as for $\sum e^{-k^2/n}\sim \int\_0^\infty e^{-x^2/n}dx=\frac12 \sqrt{\pi n}$. I do not know whether the sum $\sum p\_k$ may be simplified. 


Now the claim. We need to prove that the probability that exactly $k$ vertices remain equals $p\_k-p\_{k+1}$. It is convenient to replace the graph to the cycle with $n+1$ vertices (it becomes a path after the first move). Fix the last removed vertex $v\_0$, and the remained set $A$, $|A|=k$, $A$ should be independent and contain at least one neighbor of $v\_0$. The probability of this event (fixed $v\_0$, $A$) equals $\frac1{\binom{n+1}{k+1}(k+1)}$. It has to be multiplied by the number of ways to choose $v\_0$ and $A$. There are $n+1$ ways for $v\_0$ and $\binom{n-k+1}{k}-\binom{n-k-1}{k}$ ways to choose $A$ after that. It remains to note that 
$$\frac{\binom{n-k+1}{k}}{\binom{n+1}{k+1}(k+1)}=p\_k,\,\,
\frac{\binom{n-k-1}{k}}{\binom{n+1}{k+1}(k+1)}=p\_{k+1}.
$$


