Problem Detail: Suppose you have a network which uses time division multiplexing (i.e. Slotted Aloha). There are $N$ nodes each transmitting in a given slot with probability $p$. I understand that the probability a node is successful in a slot is $p(1 – p)^{N-1}$. This is just a geometric distribution. But our book then says that the probability there is success in a slot (i.e. no collisions) is $Np(1-p)^{N-1}$. I don’t understand:
- What the difference between the two probabilities (how is the probability that a node is successful in a slot different from the probability of success in a slot).
- Why you need to multiply the probability by the number of nodes $N$ since $p(1 -p)^{N-1}$ gives you the probability that one node transmits and all other nodes don’t transmit. Could it be because this is the probability that node might transmit given that all other nodes don’t transmit, which isn’t guaranteed. But we want to find the probability that any of the nodes transmit when all other nodes don’t transmit – hence the multiplication by $N$?
Asked By : George Robinson
Answered By : D.W.
There are $N$ slots. The book is calculating the probability that you succeed in at least one of the $N$ slots. The value $N p (1-p)^{N-1}$ is an approximation for the probability that you succeed in at least one of the slots. Strictly speaking, this formula isn’t quite right. The correct formula for the probability you succeed in at least one of the $N$ slots is $$1-(1-p(1-p)^{N-1})^N.$$ That formula is obtained as follows: the probability you fail in any single slot is $1-p(1-p)^{N-1}$, so the probability that you fail in all $N$ slots is $(1-p(1-p)^{N-1})^N$. The probability you succeed in at least one slot is one minus that. That’s how you can calculate the probability of success in at least one of the $N$ slots precisely. However, if $p(1-p)^{N-1}$ is sufficiently small (much smaller than $1/N$), then $N p (1-p)^{N-1}$ is a reasonable approximation to that probability.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32848 Ask a Question Download Related Notes/Documents
