Let $X_1,X_2,\dots,X_n$ be independent uniform variables in the square. What is the number of piece-wise linear paths which vertices are all the $X_i$ and that do not self-intersect? In other words, how many cyclic permutations $\sigma$ of $[n]$ satisfy: $[X_{\sigma(i)},X_{\sigma(i+1)}]$ and $ [X_{\sigma(j)},X_{\sigma(j+1)}]$ don't intersect in their interiors, for $1\leq i,j\leq n-1$? I am only interested in an upper bound.
My first impression is that this number's growth is at most geometric: Since there are $(n-1)!$ cyclic permutations, the result is $(n-1)!\mathbb{P}(\Omega_n)$ where $\Omega_n $ is the event that the path $[X_1,X_2],[X_2,X_3],\dots,[X_n,X_1]$ is not self-intersecting. We also have $\mathbb{P}(\Omega_n)\leq p_1\dots p_{n-1}$, where $$p_k=\mathbb{P}([X_k,X_{k+1}]\text{ intersects none of the }[X_i,X_{i+1}],i<k | \text{the path }X_1,...,X_k\text{ is not self-intersecting}).$$ I believe that this last probability is (at most) in $C/k$, which would yield the announced geometric bound.
