2
$\begingroup$

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!

  • 0
    @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.2011-05-03

4 Answers 4

0

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

1

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.

  • 0
    @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.2011-05-02
1

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

  • 0
    This will still correspond to a geometric distribution, but with a different parameter; hint: $2^{2k} = 4^k$.2011-04-29
1

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

  • 0
    Alternatively, $E(X)$ can be written in terms of the Jacobi theta function: $E(X)=\frac1{2q^{1/8}}\vartheta_2(0,\sqrt{q})$2011-04-29