= Convex-chain probability in a triangle
{title2=$\mathbb P(k\text{ sampled points form a chain})=\frac{2^k}{k!(k+1)!}$}
For independent uniform points in $0\leq y\leq x\leq1$ with the two diagonal endpoints, the displayed formula is exact. Order the $k$ intermediate points so that both coordinates increase, and write the $k+1$ positive coordinate spacings as $(u_i)$ and $(v_i)$, with each sum equal to one. The two spacing vectors have uniform simplex measure, independently, and the full ordered-coordinate region has volume $1/(k!)^2$. Simultaneous permutation of the spacing pairs preserves that measure, so all $(k+1)!$ orders of the ratios $v_i/u_i$ have equal volume. Strictly increasing ratios characterize a convex chain and automatically place the intermediate points below the diagonal. Thus its ordered volume is $1/((k!)^2(k+1)!)$. There are $k!$ ways to assign labels, and uniform triangle density is $2^k$, giving the formula. Consequently the <first moment method> bounds the probability of any length-$k$ chain among $n$ points by $\binom nk2^k/(k!(k+1)!)$.
Back to article page
