Particularly in routing packets, how does this chernoffs bound helps in reducing network congestion?
In your study, you need a probability that can refine by indicator variables. For example The probability that the adversary stores a number of common bits. If a beacon node broadcasts a random bits, Let A ⊂{1, 2,...,a} be the set of indices of the stored bits by the adversary and B the set of indices of the commonly stored bits by two neighboring sensor nodes with size |B|=l. Let B be a multi-set with l elements randomly chosen one by one from {1,2,...,a} with replacement. Let X_i be the indicator random variable for whether the ith chosen element of B is in A, i = 1,…,l. We have |A∩B^' |=X_1+⋯+X_l. Let m(h)=E[exp(hX)] denote the moment generating function and c(h):=ln〖m(h)〗 denote the cumulant-generating function. Since X_i’s are independent, the moment generating function of 〖X=X〗_1+⋯+X_l may be expressed as exp〖[l.c(h)〗] . Simple inequalities similar to
E[exp〖(h〗 X)]≥E[exp〖(hX)1(X≥μ+δ)]≥e^hX(μ+δ) P(X≥μ+δ)〗,
identify the role of moment generating function in Chernoff bound inequality.
Please check the Wikipedia entries for those concepts, they are quite good:
http://en.wikipedia.org/wiki/Chernoff_bound
http://en.wikipedia.org/wiki/Moment-generating_function
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability
- Probability Theory