# Probability of collision in binary exponential backoff

Four stations are trying to transmit frames through a single channel (only one frame per channel). After each frame is sent, they contend for the channel using Binary Exponential Backoff.

After $i$ collisions, each station waits (backs off) for a random number of slots chosen uniformly between 0 and $2^i - 1$: For the first collision, each sender will wait 0 or 1 slot times. After the second collision, the senders will wait anywhere from 0 to 3 slot times (inclusive). After the third collision, the senders will wait uniformly from 0 to 7 slot times (inclusive), and so forth. As the number of retransmission attempts increases, the contention window grows exponentially.

What is the probability of a collision on the i'th attempt?

A collision occurs if multiple stations choose the same slot. Equivalently, no collision occurs if they all choose a different slot. Assume that the four stations chose independently from one another. Let each number be represented by the uniformly distributed random variables $X_i, i=1\dots 4$.
The question is how you define the $i$'th event. I assume the question is asking for $1-P(X_1 \neq X_2 \neq X_3 \neq X_4)$ (meaning all different numbers). Defining $N=2^i$, this probability is equal to $1-\frac{N (N-1) (N-2) (N-3)}{N^4}$ since there are $N(N-1)(N-2)(N-3)$ ways of choosing four different numbers uniformly from a range of $N$. As a sanity check, if there were only two stations in the first collision, they would have to wait either 0 or 1 slot each. A collision would occur if they both chose 0 or both chose 1. This happens with probability 0.5 (2 out of the 4 possibilities). Our equation gives $1-\frac{2 \cdot 1}{2^2} = 0.5$
• I defined $N=2^i$ as the range of the uniform random variables. Am I missing the question? – Emre Apr 21 '11 at 19:10