Consider a system where time is slotted, and assume that each time slot there are $S$ available boxes; these boxes are not the same from slot to another.
Suppose there are $N$ users, each of which has a probability $p$ of having something to send at a slot.
If a user has something to send at slot $t$, then he randomly chooses a box (from the $S$ boxes) at each of slots $t$, $t+1$ and $t+2$; so in total he chooses 3 boxes.
For a user of interest, a collision occurs if at each of the slots $t$, $t+1$ and $t+2$ at least one of the other ($N-1$) users makes the same choice of box as the user of interest.
Question: What is the collision probability of other users with the user of interest?
My attempt:
- Let $P_c$ denote the collision probability. Let $P_{nc}$ be the probability of no collision, so $P_{c}=1-P_{nc}$.
- There is no collision between the user of interest and any other user if: (a) the latter one does not send in at least one of the slots $t$, $t+1$ or $t+2$, (b) the latter one sends in each of the slots $t$, $t+1$ and $t+2$, and makes the same choice of box as the user of interest at each of these slots.
- If $P_{nc,i}$ denotes the no-collision proability of user $i$ with the user of interest, we have $P_{nc,i} = 1-p^3 + p^3 (\frac{S-1}{S})^3$, where $1-p^3$ represents the probability of (a) and $p^3 (\frac{S-1}{S})^3$ represents that of (b).
- Thus, $P_{nc}=P_{nc,i}^{N-1}$, and $P_{c}=1-P_{nc,i}^{N-1}$.
I still do not understand the chance a user chooses a ball at time $t+1$. Is it $p$? Is it the chance he didn't start at $t-1,t$ or $t+1$ where he can't overlap, so $1-(1-p)^3$? Could he start at both $t$ and $t+1$ and choose two at time $t+1$?
Whatever it is, call it $q$ that any given user chooses a box at any time. Assuming our user chooses a box at each of $t,t+1,t+2$, the chance he has a match with a given other user at time $t$ is $\frac qS$. The chance he has no match with any other user is then $(1-\frac qS)^{N-1}$. The chance of a match is $1-(1-\frac qS)^{N-1}$ at each time slot, so the chance of three successive matches is $(1-(1-\frac qS)^{N-1})^3$