GATE IT 2006 | Question: 68

Question

On a wireless link, the probability of packet error is $0.2$. A stop-and-wait protocol is used to transfer data across the link. The channel condition is assumed to be independent of transmission to transmission. What is the average number of transmission attempts required to transfer $100$ packets?

• A. $100$
• B. $125$
• C. $150$
• D. $200$

Comments

The question could be easily solved if you know the concept of the LAW OF TOTAL EXPECTATIONS.

E is the expected no. of tries to get success.

                                ┌─────── success →  e=1 (in a single attempt we sent)
      E     ───────┤
                                └─────── Error →  e=1+E (1 attempt wasted; restart)

so E=P(success)⋅1+P(error)⋅(1+E)

so E=1/P(success)

We know expectation acts like the average with enough sample size.

so for sending 1 frame successfully we need 1/P(success)

so for 100 frames we need 100/P(success) attempts

so 100/0.8=125 (B)
option B is correct 

---

If the error rate is 20%, it means that out of every 10 packets you try to send, only 8 will be successful on average.

To get 100 successful packets, you can set up a simple ratio:

 

$$\frac{8 \text{ success}}{10 \text{ total}} = \frac{100 \text{ success}}{x \text{ total}}$$

$$x = \frac{100 \times 10}{8} = \mathbf{125} \text{}$$

---

This Question is based on "Geometric distribution & Linearity of expectation" of Probability

Probability of packet error, $p = 0.2$

Probability of successful transmission, $p_s = 1 - p = 1 - 0.2 = 0.8$

The number of attempts $X$ required to successfully transmit a single packet follows a Geometric Distribution with success probability $p_s$:

$P(X = k) = (1 - p_s)^{k-1} \cdot p_s = p^{k-1}(1 - p) \quad \text{for } k = 1, 2, 3, \dots$

The expected value (mean) of a geometrically distributed random variable $X$ is,

$E[X] = \sum_{k=1}^{\infty} k \cdot P(X = k) = \frac{1}{p_s}$        -------------------> (1)

Derive the Expectation of geometric distribution 

Note : There multiple method to find expectation 1) Calculus method 2) Recursive method Using Law of expectation (Most famous) 3) Combinatorial Approach.

Derive Using Calculus Method 

Let $X$ be a geometrically distributed random variable representing the number of independent trials required to obtain the first success, with success probability $p_s \in (0, 1]$ and failure probability $q = 1 - p_s$.

The PMF of $X$ is:

$P(X = k) = (1 - p_s)^{k-1} p_s = q^{k-1} p_s \quad \text{for } k = 1, 2, 3, \dots$

Expected Value = $E[X] = \sum_{k=1}^{\infty} k \cdot P(X = k) = \sum_{k=1}^{\infty} k \cdot q^{k-1} p_s$$

=> $E[X] = p_s \sum_{k=1}^{\infty} k q^{k-1}$

We know that  standard infinite geometric series for $\vert{}q\vert{} < 1$,

=> $\sum_{k=0}^{\infty} q^k = \frac{1}{1-q}$

Differentiating both sides with respect to $q$,

=> $\frac{d}{dq} \left( \sum_{k=0}^{\infty} q^k \right) = \frac{d}{dq} \left( \frac{1}{1-q} \right)$. [ Most Important derivatives you can find in Heap in data structure for calculate TC of Bottom up .]

=> $\sum_{k=1}^{\infty} k q^{k-1} = \frac{1}{(1-q)^2}$

put the value  into the expectation formula

=> $E[X] = p_s \cdot \frac{1}{(1-q)^2}$

Since $1 - q = p_s$,

 $E[X] = p_s \cdot \frac{1}{p_s^2} = \frac{1}{p_s}$

put the value of  $p_s = 0.8$ in equation (1)

$E[X] = \frac{1}{0.8} = \frac{10}{8} = 1.25 \text{ attempts per packet}$

Apply Linearity Of Expectation 

The total expected number of transmission attempts $T$ for $N = 100$ independent packets is the sum of the expected attempts for each individual packet.

$E[T] = E\left[\sum_{i=1}^{100} X_i\right] = \sum_{i=1}^{100} E[X_i] = 100 \times E[X]$

$E[T] = 100 \times 1.25 = 125$

Answer 1

Consider that we have to send $N$ packets and $p$ is the error probability rate. Error rate $p$ implies that if we are sending $N$ packets then $N\times p$ packets will be lost and thus we have to resend those $N\times p$ packets. But the error is still there, so again while resending those $N\times p$ packets, $N\times p\times p$ will be further lost and so on. Hence, this forms a series as follows:

$N + N\times p + N \times p^2 + \ldots$
$=N(1 + p + p^2+\ldots$
$=\dfrac{N}{1-p} \text{(Sum to infinite GP series)}$

Now we are having $N=100$ and $p=0.2,$ which implies $125$ packets have to be sent on average.

Correct Answer: $B$

Comments

@AakS @Gate Fever Why are we not considering the error possibilities in case of ACKs sent in response to the packet transfers? It could very well be the case that the ACK for a packet gets lost and we need to resend the packet again.

---

Let x be the number of additional retransmissions.

We have success probability = 1 - 0.2 = 0.8

100 packets are sent successfully, so we have,

$\frac{100}{100+x}$ = 0.8

Solving the above equation, we get x = 25.

Total number of transmissions = 100 + x = 100 + 25 = 125

---

Similar question –

On a coin toss, P(H) = 0.8 and P(T) = 0.2. What is the expected number of tosses for one head to come?

$= \frac{1}{P(H)} $ (Can be proved)

Expected number of tosses for 100 heads = $= \frac{1}{P(H)}  \times 100 = \frac{1}{0.8}  \times 100 =125$ (By Linearity of Expectation)

Answer 2

Total number of re-transmissions for one frame, in general, is $\dfrac{1}{(1-p)}$
where $p$ is the probability of error.

So here it would be

for one frame $\dfrac{1}{(1-0.2)}$

So for $100$ frames $\dfrac{100}{(0.8)}=125$

Comments

I am not getting this 1/(1-p). . plz explain

---

//I think this is how it was obtained:

 

//Assume that it took x attempts to transmit 100 packets,

// one successful attempt = 1 successful packet transfer.

 

 => x - (20/100)x = 100

      ^         ^                 ^

      |            |                  |---------------- total packets transmitted.    

      |            |------------   attempts that failed.

   total attempts.                    |      

      |_______________________|

                            |

                        successful attempts

 => x = 100 / (1 - .2)                                      

 i.e. x = n / (1 - p)

---

Let E be the expected number of retransmissions for a packet and p be the probability that packet is sent without an error.

E = 1*P + (E+1)*(1-P)

   = P + E - EP + 1 - P

   = 1 / P

 Here it is  = 1 / 0.8

Answer 3

Let random variable X is 1 . (A function which map a packet to a real number 1)

And probability of it's success is given is 0.8..

E = 0.8 * 1 + 0.8 * 1 +... n_packest = 100   (we expect 100 packets to get transmitted successfully)

=> 0.8 * 1 * n_packet = 100

=> n_packet = 125...

So, if we transmit 125 packets then we can expect 100 packets got transmitted successfully!! And this is average number of transmission attempts required!!

 

So, option (B)

Comments

$E[100*X] = 100*E[X]$

Answer 4

I found this much simpler.

$N=>$   Total packets to be sent

$0.8*N=>$   Total packet to be sent successfully , each with probability of   $0.8$

So,

$0.8*N=100$

$N=125$

So total 125 attempts are required to send 100 packets if probability of success of each packet is $0.8$

Comments

i dont think u mentioned him correctly

his name is not coming in blue color

---

as per my knowledge, we have to take ceil value but not fractional value

" it will be "ceil " value i guess coz i think fractional part means some of the data it still need to be transferred hence 1 more packet will be required. " --- absolutely correct as per my knowledge

---

ok,thanks

Answer 5

Given-

• Probability of packet error = 0.2
• We have to transfer 100 packets

 

Now,

• When we transfer 100 packets, number of packets in which error will occur = 0.2 x 100 = 20.
• Then, these 20 packets will have to be retransmitted.
• When we retransmit 20 packets, number of packets in which error will occur = 0.2 x 20 = 4.
• Then, these 4 packets will have to be retransmitted.
• When we retransmit 4 packets, number of packets in which error will occur = 0.2 x 4 = 0.8 ≅ 1.
• Then, this 1 packet will have to be retransmitted.

 

From here, average number of transmission attempts required = 100 + 20 + 4 + 1 = 125.

Option (B) is correct.

Comments

Great approach

---

Nice approach

Answer 6

Using Binomial distribution we can solve this question.

If we send N packets then, expected number of successful(error free) transmission will be  N*0.8 (Expectation of binomial distribution=NP, where N= no. of trials and P=probability of success) .

We need to send 100 packets successfully, So,  N *0.8 =100 .... or, N= 100/0.8 = 125  Answer B

Hence if we send 125 packets then , expected number of error free packets will be 100.

Comments

$N$ is the number of trials required to send a single packet. So I am not too sure if we can just set $N * 0.8 = 100$. Here is how I approached it.

There will be 100 different random variables $X_i$ corresponding to the expected number of transmission attempts of 100 different packets each. Each one will have an independent binomial distribution whose expectation you have to find. The number of trials required to send a single packet can go infinitely long (you might succeed in first attempt, OR you might fail in first and succeed in second, OR you might fail in first two and succeed on the third, and so on).

Once you find $E[X_i]$, by linearity of expectation, you can sum all $E[X_i]$ and get $E[X]$, which is the expected number of transmission attempts for 100 packets.

All $E[X_i] = 5/4$, and $E[X] = 5/4 * 100 = 125$.