# Simple mean number of rounds probability question

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!

-
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

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

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

-
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).

-
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

-