1
$\begingroup$

I'm struggling with a communications math problem.

A stream of data is transmitted. For the first transmitted packet, the packet error rate (PER) is $0.1$, but for every following transmission, the PER will be less. I have to figure out the necessary PER for an average number of transmission attempts of $1.105$ . This includes the successful one.

My intuition is the following:

$N = 0.9 * 1 + 0.1*(1-PER) * 2 + 0.1*PER*(1-PER)*3 + 0.1*PER*(1-PER) *4 \cdots $

$N =$ average number of transmission attempts

This, I think, will yield the correct result. But apparently, and I just can't figure out why, this is equivalent to

$N = 1 + 0.1 + 0.1*PER + 0.1*PER*PER + \cdots = 1 + 0.1(1+p+p^2 + \cdots)$

Can anyone please explain this to me? What's the idea behind it? My stochastics is not the best.

$\endgroup$
5
  • $\begingroup$ Your first sum is telescoping to the second. Work out the products of the terms of your first sum, and you'll see that there is partial cancellation going on between successive terms. $\endgroup$
    – Raskolnikov
    Nov 17, 2017 at 11:28
  • $\begingroup$ $N = 0.9 + 0.2 - 0.2*x + 0.3*x - 0.3*x^2 + 0.4*x^2 - 0.4*x^3 + 0.5*x^3 - 0.5*x^4 + \cdots = 1.1 + 0.1*x + 0.1*x^2 + 0.1*x^3 + \cdots$ . Thx so much ! I can see the link between these two formulas now. But my intuition is still not clear: The second formula is simply adding the probabilities: First, that there is no error, then one error, then two, and so on. How can adding probabilities yield the average number of transmissions? .. well, but mathematically it's fine. $\endgroup$
    – Luk
    Nov 17, 2017 at 12:18
  • $\begingroup$ It's not just probabilities, it's probability times the average amount of errors for one packet which is 1. At least, I suppose that is it, because since you didn't give enough context to the question, I can't even figure out how you arrived at the first formula. $\endgroup$
    – Raskolnikov
    Nov 17, 2017 at 12:26
  • $\begingroup$ sorry, I knew the question was a little cryptic. We are actually not given much context either. To figure out the formula, I drew a tree where there are 4 nodes. The first node has one branch going to 1 indicating the first transmission attempt. It is successfull with 90% probability. The second branch goes to the second node and has a 10% probability written on it, indicating an error. From this node goes one branch to the 2 (2nd transmission attempt which is then successfull) with a probability of (1-PER). Another branch goes to the third node with a probability PER. $\endgroup$
    – Luk
    Nov 17, 2017 at 13:26
  • $\begingroup$ Well and in the second formula, the 1, I think, is just saying that we have one transmission for sure. $\endgroup$
    – Luk
    Nov 17, 2017 at 13:27

1 Answer 1

Reset to default
0
$\begingroup$

I've figured out your question. Let's start with the meaning of the first formula and let's tidy up your notation a little bit. What you're trying to do is to transmit a packet without error. And you keep trying until it is transmitted errorless. Since the packet error rate or $\text{PER}$ is $0.1$, you need a few tries. The probability of succeeding after $k$ tries is

$$P[N=k]=(1-\text{PER})\cdot\text{PER}^{k-1}$$

Indeed, if you succeed in $k$ tries, that means you have failed $k-1$ times to transmit the package and finally succeeded the $k$th time. Hence this formula for the probability. This is known as a geometric distribution in statistics and probability theory.

Then, we want to know the average number of tries

$$E[N]=\sum_{k=1}^{\infty} k\cdot P[N=k] = \sum_{k=1}^{\infty} k \cdot (1-\text{PER})\cdot\text{PER}^{k-1} \\ = 1\cdot (1-\text{PER}) + 2 \cdot (1-\text{PER}) \cdot \text{PER} + 3 \cdot (1-\text{PER}) \cdot \text{PER}^2 + \ldots$$

This is exactly your first formula, derived from the definition of average or expected number of tries for the geometric distribution.

But let's look at it from another viewpoint. Imagine step by step, we look at what the average can be. Well, you have to do at least one try, so

$$E[N]=1+\ldots$$

But that try might fail, with probability $\text{PER}$, so with probability $\text{PER}$ you need to make another try, so on average $\text{PER}$ new tries extra

$$E[N]=1+\text{PER}+\ldots$$

But that new try might also fail, thus you need to make a new try again with probability $\text{PER}$, but since the previous step was already on average $\text{PER}$ you now add $\text{PER}^2$

$$E[N]=1+\text{PER}+\text{PER}^2+\ldots$$

Etc... This will get you your second formula. This can be however condensed in a neat way:

Since your first try will either succeed, either fail, in the case you succeed, you'll make $1$ try in total and that's it. But in the case you fail, you make $1$ try and then you're still nowhere, you have to keep trying. But since the errors are independent of each other (or at least they are assumed to be), at that point, on average the number of extra tries you'll have to do is exactly the same as if you hadn't already done a try. Thus, we can resume this as follows:

$$E[N] = (1-\text{PER}) \cdot 1 + \text{PER} \cdot (1+E[N])$$

and you can work this out to be

$$E[N] = 1+ \text{PER} \cdot E[N]$$

If you keep susbtituting back the formula into itself, you get your second formula. If however you just rearrange the equation to take out $E[N]$ in function of $\text{PER}$ you get

$$E[N] = \frac{1}{1-\text{PER}}$$

And this is probably the most compact and convenient of all the formulas. Maybe you'll remember this from Taylor series courses.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .