Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If the probability that something happens in the Kth round is (1-1/(2^k)) what is the mean number of rounds that it will take for it to happen? I know it means if you did it a bunch of times what the average number of rounds would be, but it's different than going until the sum is 50% I guess. How do I do this? Thanks!

share|improve this question
    
And how would things change if I want 1-1/(2^(2k))? –  Josh Apr 29 '11 at 5:04
    
You should indicate whether Didier or I read the problem correctly. The answer is different in the two cases. –  Ross Millikan Apr 29 '11 at 12:50
    
@Ross I posted what I ended up using as the answer. I didn't completely understand you're guys answers, so I can't say who interpreted it better. –  Josh May 3 '11 at 19:14

4 Answers 4

up vote 1 down vote accepted

Since the numbers $p(k)=1-1/2^k$ (or $p(k)=1-1/4^k$) sum to more than $1$, $p(k)$ cannot be the probability that round $k$ is the successful round and the question as written by the OP makes no sense.

To save the day, let us assume instead that $p(k)$ is the probability that round $k$ is the successful round, knowing that rounds $1$ to $k-1$ were not. In other words, the successful round $X$ is such that $$ P(X=k|X\ge k)=p(k). $$ From here the OP could (should?) try to show that the distribution of $X$ is given by $$ P(X=k)=p(k)\prod_{i=1}^{k-1}(1-p(i)). $$ or, equivalently, by $$ P(X\ge k)=\prod_{i=1}^{k-1}(1-p(i)). $$ Going back to the question asked, let us recall that the expectation of $X$ can be computed in at least two different ways, since $$ E(X)=\sum_{k=1}^{+\infty}kP(X=k)=\sum_{k=1}^{+\infty}P(X\ge k). $$ Plugging $p(k)=1-q^k$ (with $q=1/2$ or $q=1/4$, apparently) into the second formula yields $$ E(X)=\sum_{k=1}^{+\infty}\prod_{i=1}^{k-1}q^{i}=\sum_{k=1}^{+\infty}q^{k(k-1)/2}, $$ which, as a specialization of Ramanujan theta function, is also $$ E(X)=\frac{(q^2;q^2)_\infty}{(q;q^2)_\infty}. $$

share|improve this answer
    
Alternatively, $E(X)$ can be written in terms of the Jacobi theta function: $E(X)=\frac1{2q^{1/8}}\vartheta_2(0,\sqrt{q})$ –  J. M. Apr 29 '11 at 13:47

If the probability of ending on the $k^{\text{th}}$ round is $p(k)$ the mean number of rounds is $\sum_{k=1}^{\infty}kp(k)$. In your case, presumably you stop when the event happens (otherwise your probabilities sum to much more than $1$). The probability of round $k$ is then $(1-2^{-k})-(1-2^{k-1})=2^{-k}$ so you need $$\sum_{k=1}^{\infty}k2^{-k}$$ You are right this is not when the sum reaches $50\%$, as that happens on the first round.

share|improve this answer
    
I don't understand how you get p(k); you said it is the probability of ending on the kth round, so wouldn't that be 1-(1-1/2^0)...-(1-1/2^(k-1)-(1-1/2^k) –  Josh Apr 29 '11 at 4:44
    
Ross: I do not get your $(1-1/2^k)-(1-1/2^{k-1})$ argument either. See my post for another (more logical, I think) interpretation of the question. –  Did Apr 29 '11 at 5:57
    
@Didier: Shai and I read it the same way. I agree it could go either way. –  Ross Millikan Apr 29 '11 at 12:48
    
Sorry but, since there is no explanation about this in Shai's answer either, this is not an answer. I genuinely wonder what reason led you to make $p(k)-p(k-1)$ enter the picture, other than the fact that since $p(k)\to1$ when $k\to+\infty$ and $p(0)=0$ they sum to one. –  Did May 2 '11 at 8:24
    
@Didier: I read it that way because it made the probabilities sum to 1 and seemed simple. As you got the checkmark, presumably you were correct. –  Ross Millikan May 2 '11 at 13:05

To add on Ross Millikan's answer, note that $1 - 1/2^k$ corresponds to the distribution function of the geometric distribution with parameter $1/2$. Indeed, for $X \sim {\rm geometric}(1/2)$, $$ {\rm P}(X \leq k) = \sum\limits_{i = 1}^k {{\rm P}(X = i)} = \sum\limits_{i = 1}^k {\frac{1}{{2^i }}} = 1 - \frac{1}{{2^k }}, \;\; k=1,2,\ldots. $$ Thus, the question actually asks for the mean of the geometric($1/2$) distribution.

EDIT: In fact, given the distribution function of an arbitrary nonnegative integer-valued random variable $X$, one can find ${\rm E}(X)$ immediately as follows: $$ {\rm E}(X) = \sum\limits_{k = 0}^\infty {{\rm P}(X > k)} = \sum\limits_{k = 0}^\infty {[1 - {\rm P}(X \le k)]}. $$ In our example, where ${\rm P}(X \le k) = 1 - 1/2^k$, $k=0,1,2,\ldots$, we thus get $$ {\rm E}(X) = \sum\limits_{k = 0}^\infty {\frac{1}{{2^k }}} = 2. $$ More generally, if ${\rm P}(X \le k) = 1 - q^k$, $k=0,1,2,\ldots$, $0 < q < 1$ fixed, we get $$ {\rm E}(X) = \sum\limits_{k = 0}^\infty {q^k} = \frac{1}{{1 - q}}. $$ Now, put $p=1-q$, and recall that the geometric($p$) distribution has mean equal to $1/p$. In particular this gives the answer to your second question (in the comments).

share|improve this answer
    
And how would things change if I want 1-1/(2^(2k))? –  Josh Apr 29 '11 at 5:04
    
This will still correspond to a geometric distribution, but with a different parameter; hint: $2^{2k} = 4^k$. –  Shai Covo Apr 29 '11 at 5:20

Using the first round where both send with probability 100% as round 1 instead of round 0. The probability that each sends at the same time and collides is 1/(2^(k-1)). Thus the probability of success at each round k is 1-(1/(2^(k-1)). The probability that the contention ends after k rounds is probability of collision on each round up to k, and no collision on round k. The mean number of rounds if there is no upper limit established, is enter image description here

share|improve this answer

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.