Let's say I want to deliver a file of $2Kb$ over a network channel from A to B, where A can transmit in a transfer rate of R bits-per-second (let's ignore other parameters like propagation time, for the sake of argument).
And let's say that the channel is quite noisy: when you deliver a bit in that channel, it will be flipped (or "corrupted", if you will) with probability $p$.
I want to calculate two things:

  1. The probability to successfully deliver the file from A to B.
  2. The expected time (time expectancy? not sure what exactly the English term is...) to deliver the file. Or to put it simply: on average, how much time does it take...

the first one is not too hard; the probability to successfully deliver one bit from A to B is $1-p$, so successfully delivering the file will be $(1-p)^{\#bits\_in\_file}=(1-p)^{2048}$.

I'm not sure about 2 though.
I know the time to send a file from A to B is $\frac{\#bits\_in\_file}{transfer\_rate}=\frac{2Kb}{R}$.

The answers to 2 say: $ (delivering\_time)\times \frac{1}{prob\_of\_success}=(\frac{2Kb}{R})\frac{1}{(1-p)^{2048}}$.

My question is: why is it the answer? How do you even calculate such thing? I know how to calculate an expected value given a random variable, but I can't see it here.

  • $\begingroup$ By linearity and independence, the expected time for the file transfer is just $\frac{1}{1-p}$ times the time required in a perfect channel (no corruption). $\endgroup$ – Jack D'Aurizio Dec 13 '14 at 21:29

This is because we are transmitting the file with a geometric distribution on each variable, i.e. we can model transmitting one bit with a geometric distribution $N \sim \text{Geo}(1-p)$, as we keep transmitting the bit until it is transmitted succcessfully.

Thus we have intuitively that the mean expected number of bits that need to be transferred is given by:

$$\nu= \sum_{n=1}^{2048}\mathbb{E}[N]=\frac{2048}{1-p}$$

Where we use the known fact that if $X \sim \text{Geo}(p)$, then $\mathbb{E}[X]=\frac{1}{p}$. And thus the expected total time would be given by:

$$\tau = \frac{\nu}{R}=\frac{2048}{R}\cdot\frac{1}{1-p}$$

If we look at the problem using the Negative Binomial Distribution, we have that the entire file can be expressed using the random variable $N \sim \text{NB}(2048,p)$, we therefore have that:

$$\nu = \mathbb{E}[N] + 2048 = \frac{2048\:p}{1-p} + 2048 = \frac{2048p + 2048 - 2048p}{1-p}=\frac{2048}{1-p}$$

Where we have to add $2048$ to the expected value of $N$ as the Negative Binomial Distribution is effectively measuring the number of bits that we have to resend. And thus we get the same as before:

$$\tau = \frac{\nu}{R}=\frac{2048}{R}\cdot\frac{1}{1-p}$$

  • $\begingroup$ Ohh! geometric distribution. didn't see that... But... shouldn't it be Negative binomial distribution then? Because we "roll a dice with probability $p$ until $k$ successes", aren't we? $\endgroup$ – so.very.tired Dec 13 '14 at 21:41

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.