Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
The etiquette requires to give cross-references when posting here and on MSE simultaneously. So, please do it in the future. The link is math.stackexchange.com/questions/305442/… –  fedja Feb 16 '13 at 12:11
add comment

2 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.