What is the probability for sequence of lenght L in subset of [n]

Question

I am trying to calculate the probability that i'll have L length sequence in a random subset of [n] when the subset size is k. for example, if n=5, k=4 and L=2 I'll have the below subsets: {2,3,4,5}, {1,3,4,5}, {1,2,4,5}, {1,2,3,5}, {1,2,3,4} and the answer will be 1/5 because there is only one subset that have L=2 suqence or for L=3 the anser will be 2/5 etc.

Answer 1

Let $f(n,k,L)$ be the number of $k$-element subsets of $\lbrace 1,2,\dots,n\rbrace$ containing no $L+1$ consecutive integers. Then $$ \sum_{n,k}f(n,k,L)x^{n+1}y^k = \frac{1-xy}{1-x-xy-x^{L+2}y^{L+1}}. $$

Answer 2

I suspect that an exact answer for general $k$ and $n$ will be hard to come by. However, you should be able to get very good approximations for most $k$ and $n$: in fact, the probability will usually be either approximately 0 or approximately 1.

It's usually much easier to work with the space of subsets of $[n]$ where each element is retained with probability $k/n$. This brings in useful independence, but typically doesn't have too much effect on the probabilities of events of interest.

This independence can be exploited using standard results on concentration of measure. My answer to this related question describes how Talagrand's inequality can be applied in cases like this.

Talagrand tells you that the number of sequences of length $L$ is tightly concentrated about its mean, so if the expected number of sequences of length $L$ is large then the probability that there is such a sequence is close to 1. If the expected number of sequences of length $L$ is small (much less than 1), then the probability that there is such a sequence is close to 0 as $\mathbb{P}(X \geq 1) \leq \mathbb{E}(X)$.

There are lots of things to check, but concentration inequalities are always worth trying in cases like this (where you have lots of independence, or can force some independence with little loss) if you're happy with asymptotic results.