$\frac{1}{2^1}*\frac{1}{2^2}*\frac{1}{2^3}*......*\frac{1}{2^{k-1}}*\frac{2^k-1}{2^k}$

= $\left \{ \prod_{x=1}^{k-1}\left ( \frac{1}{2^x} \right ) \right \}*\frac{2^k-1}{2^k}$

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

Two CSMA/CD stations are each trying to transmit long (multiframe) files. After each frame is sent, they contend for the channel, using the binary exponential backoff algorithm. What is the probability that the contention ends on round k?

- $\Sigma kP_k$
- $kP_k$
- $\Sigma P_k$
- none

0 votes

After k consecutive collisions (with probability p), a station delays retransmission by a random interval uniformly distributed between 0 and 2^{k }, (so the packet is transmitted k+1 times in total).

Number the attempts starting from 1. Attempt i is distributed among 2^{i−1} slots . Thus, the probability of a collision on attempt i is 1/(2^{i−1}) or^{ }2^{−(i−1)}. The probability that the first k-1 attempts will fail is then:

P_{k} = (1 − 2 ^{−(k−1)}) · $· \prod (i=1 to ( k-1)) $ 2^{ −(i−1)} , which can be simplified to:

P_{k }= (1 − 2 ^{−(k−1)}) · 2 ^{− ((k−1)·(k−2)) /2 },

so, the expected number of rounds is simply: $\sum_{k}^{}$k.P_{k}

So, the answer is **(A)**

Ref: http://omikron.eit.lth.se/ETSN01/ETSN01/tutorials/Tutorial8.pdf

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,084 questions

45,574 answers

132,084 comments

49,063 users