2
$\begingroup$

I have a parameter $q$ which is the probability of selecting a vertex (among $n$ vertices...) to be in a certain set.

I am constructing the sets in an iterative way, having the vertex $v_i$ be in the set with probability $\leq \left(1 - q\right)^i$ (I'm not going into details about the order of the vertices for which this is performed, as I don't think its vital).

By that I can tell that the expected size of my set is $\Sigma_i \left(1-q\right)^i$.

Now the part which baffles me is where it says: $$\Sigma_i \left(1-q\right)^i = O\left( \frac{1}{q} \right)$$

So I know $q$ represents the probability for a vertex to be selected. So $q<1$.... But as I recall the formula for the sum of a geometrical series is:

$$\frac{a_1 \cdot \left( \left(1-q\right)^i -1\right)}{1-q-1} = \frac{\left(1-q\right) \cdot \left( \left(1-q\right)^i -1\right)}{-q}$$

Seems more like $O\left( q^i \right)$ than $O\left( \frac{1}{q} \right)$.

This is a silly question, but I would like to know where I got confused...

$\endgroup$

1 Answer 1

8
$\begingroup$

There is an abuse of notation in your question: you are using $i$ as both the index for the summation and as the total number of terms in the sum (in the closed formula).

Anyway, the ratio of the geometric series is $1-q$, but you mixed it up with $q-1$ in the closed formula. For simplicity consider the infinite sum $\sum_{i=0}^{\infty} (1-q)^i$, which is clearly an upper bound to the quantity you are after (and only affect the result by a multiplicative constant): $$ \sum_{i=0}^{\infty} (1-q)^i = \frac{1}{1 - (1-q)} = \frac{1}{q}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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