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

In the middle of page 9 of http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf.

They said " Now we select a random subset....choosing lines independently with probability $\frac{Q}{100}$. With positive probability....

I can not see why there is positive probability...

Could any one explain a bit about what is going on there? I feel they are applying large number law, but I can not see it clearly, for example what is the probability measure space, what is the random variables, how the law is used?..

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Not a complete answer but a quick explanation of how I read page 9 in that paper.

  1. The underlying probabilistic model is that for every line $l\in\mathfrak L'$ you throw a coin that shows head with probability $100/Q$ and tail with probability $(Q-100)/Q$, and then $\mathfrak L''$ is the set of all lines whose coin showed head. In other words, you choose a random subset $\mathfrak L''$ of $\mathfrak L'$ and the probability for choosing a particular set $\mathfrak L_0\subseteq \mathfrak L'$ equals $$\mathbf{P}[\mathfrak L''=\mathfrak L_0]=\left(\frac{100}{Q}\right)^{|\mathfrak L_0|}\left(1-\frac{100}{Q}\right)^{|\mathfrak L'\setminus\mathfrak L_0|}.$$
  2. By linearity of expectation the expected cardinality of $\mathfrak L''$ is $\mathbf{E}(|\mathfrak L''|)=\frac{100\alpha N^2}{Q}$, and this implies $$\mathbf{P}\left[|\mathfrak L''|\leqslant\frac{200\alpha N^2}{Q}\right]\geqslant\frac12.$$
  3. We are done when we can show that the probability of the event "Every line in $\mathfrak L'$ intersects $N/20$ lines in $\mathfrak L''$" has probability at least $1/2+\varepsilon$ for some positive $\varepsilon$, since then the event "$|\mathfrak L''|\leqslant\frac{200\alpha N^2}{Q}$ and every line in $\mathfrak L'$ intersects $N/20$ lines in $\mathfrak L''$" has probability at least $\varepsilon$.

As I understand it, the intuition is that a typical line in $\mathfrak L'$ intersects a quadratic number of lines in $\mathfrak L'$ so it is highly unlikely that less than $N/20$ of these are chosen for $\mathfrak L''$.

At the moment I don't see how to make that rigorous. I haven't read the rest of the paper, yet, but my impression is that it might be convenient (or even necessary) to replace $\mathfrak L'$ by something slightly smaller, throwing away some rubbish:

  • I don't see why $\mathfrak L'$, as it is defined, cannot contain a few exceptional lines that have almost all their intersections with lines outside $\mathfrak L'$, so they intersect less than $N/20$ lines in $\mathfrak L'$. If this is the case, these lines have no chance to intersect $N/20$ lines in $\mathfrak L''$.
  • It looks easier to show that with high probability almost every line in $\mathfrak L'$ intersects $\mathfrak L''$ at least $N/20$ times (instead of "every line in $\mathfrak L'$" ). Maybe it is sufficient to replace $\mathfrak L'$ by this big subset.

Let's hope for a better answer by someone who understands what's going on.

share|improve this answer
    
Thanks Kali, I think you are right. then one can take large N to ensure the 3 by Large number law. I agree that one should work on a smaller set. –  user13289 Mar 17 '11 at 15:11
    
Hmm. I'm not really convinced by my own answer. I have to think about it some more. –  Thomas Kalinowski Mar 17 '11 at 21:45
    
in fact one can do estimate directly to see the probability is positive –  user13289 Mar 18 '11 at 1:39
    
one can do this as following Claim: suppose both $L_{1}$ and $L_{2}$ has $O(N^{2})$ lines, each line in $L_{1}$ intersects with at least almost $QN$ lines in $L_{2}$, now choosing line in $L_{2}$ independently with probability $\frac{1}{Q}$, the resulting subset of $L_{2}$ is denoted by $L_{3}$ then one has similar statement in 2: with probability bigger than 1/2 $L_{3}$ contains $\frac{O(N^{2})}{Q}$ lines for 3, the probability that a line in $L_{1}$ intersects more than $\frac{N}{2}$ lines in $L_{3}$ is bigger than $1-e^{-N/100}$ –  user13289 Mar 18 '11 at 3:21
    
this can be done by using estimate in en.wikipedia.org/wiki/Binomial_distribution. then the probability that every line in $L_{2}$ intersects with at least $\frac{N}{2}$ lines in $L_{3}$ is bigger than $(1-e^{-N/100})^{N^{2}}$, which goes to 1 when $N$ very large. –  user13289 Mar 18 '11 at 3:25
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.