I'm studying probabilistic analysis in real time network. We have learned how many attempts in average are required to transmit a packet when there is no error on the feedback channel.

With no error in the feedback

enter image description here

$p$ Probability packet not send

$1-p$ Probability packet send

$i$ transmission attempts

$Pr(n=i) = p^{i-1} (1-p)$

$E[n] = \sum_{i=1}^{\infty}i p^{i-1} (1-p)$

With some rules of derivation and geometric series :

$E[n] = \frac{1}{1-p}$

I need to extend the analysis for the case of errors in the feedback channel.

How to find how many attempts in average are required to transmit a packet when there is error in the data channel and the feedback channel?

I have tried something :

$p$ Probability packet not send

$1-p$ Probability packet send

$i$ transmission attempts

$q$ Probability ACK not send

$1-q$ Probability ACK send

$Pr(n=1) = (1-p)(1-q)$

$Pr(n=2) = p(1-p)(1-q) + q(1-p)^2(1-q)$

$Pr(n=2) = (1-p)(1-q) (p+ q(1-p))^{2-1}$

$Pr(n=i) = (1-p)(1-q)(p+q(1-p))^{i-1}$

I'm a little confused. The number of possibilities increase very fast. For 2 attempts : The data fails one time and succeeds the second time with no error in the feedback or the data succeeds in both case but the feedback fails the first time.

But when I arrive at 20 attempts the number of possibility reach $2^{i-1} = 2^{19}$. Which looks too big for me.

How can I check if I'm on the right track?

  • 2
    $\begingroup$ There does not seem to be a question here. What's the issue? Are you unable to simplify the series? $\endgroup$ – Raphael May 27 '15 at 13:21
  • $\begingroup$ In fact, I have try to find the answer. But I'm not sure if the answer is correct. My question is : My answer is it correct and if yes is it possible to simplify the series? I'll will edit my question, it'll be more clear. Thx for help. $\endgroup$ – Jérôme Detournay May 27 '15 at 13:31
  • 2
    $\begingroup$ Checking solutions for correctness is not a type of query we consider appropriate, and simplifying series is borderline offtopic; it fits Mathematics much better. $\endgroup$ – Raphael May 27 '15 at 13:51
  • 2
    $\begingroup$ This is not a platform for discussion, but for questions and answers; not because we don't like to discuss, but because the software does not work well for discussions. For discussion, visit Computer Science Chat, meet people in meatspace (recommended) or use forum software. I suggest you take that series (without most of the derivation) to Mathematics once you are reasonably certain it's correct; it does not look too hard to me (take a look at the TCS cheat sheet). $\endgroup$ – Raphael May 27 '15 at 14:11
  • 2
    $\begingroup$ Heh, you are moving along the "how to ask a question here?" chain. :D The next thing to ask would be: What have you tried? Where did you get stuck? Aaand we've come full circle. No matter where you cut, questions of the kind "help me (do|improve|check) my homework" are rarely suitable for the SE platform. What we want to see is your attempt, and a specific question about that attempt like "this step feels weird because of X, what can I do?". If you can formulate such a question about your original attempt (what specifically was the issue?), you are golden. $\endgroup$ – Raphael May 27 '15 at 15:09

Your analysis so far is correct. Let's consider the probability that it will take $k$ attempts to transmit a package. This means that there must be $k-1$ failures followed by a final success. There are two ways a transmission can fail:

  1. Transmit succeeds, ACK fails. Call this a type-1 failure. Its probability will be $(1-p)q$.
  2. Transmission fails (so ACK is not sent). Call this a type-2 failure; its probability will be $p$.

For there to be $k-1$ failures, we must have a sequence of events $E_1, E_2, \dotsc, E_{k-1}$, each of which is a failure of type 1 or type 2. The probability, then, of each $E_i$ must be the sum of the probabilities of both types of failure, namely $p + q(1-p)$. Since the events are independent, the probability of the entire sequence will be the product $(p+q(1-p))^{k-1}$. The sequence must be followed by a successful transmission and a successful ACK, so $$ Pr(n=k) = (1-p)(1-q)(p+q(1-p))^{k-1} $$ The expected number of attempts to reach a successful transmission will be $$\begin{align} E[n] &= 1\cdot(1-p)(1-q)+2\cdot(1-p)(1-q)(p+q(1-p))+\dotsm\\ &= (1-p)(1-q)[1+2(p+q(1-p))+3(p+q(1-p))^2+\dotsm]\\ &= (1-p)(1-q)\sum_{k=1}^\infty k(p+q(1-p))^{k-1} \end{align}$$ It's a more or less well-known result that $$ \sum_{k=1}^\infty kx^{k-1}=\frac{1}{(1-x)^2} $$ and so we have $$ E[n]=(1-p)(1-q)\frac{1}{(1-(p+q(1-p)))^2} = \frac{1}{(1-p)(1-q)} $$ which, as they say, is just too pretty not to be correct, not to mention that it's what we should expect, given the symmetry of the problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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