Expected Size of Independent Set

Question

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'$?

Answer 1

[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}. $$