On an Old Question of Erdős and Rényi Arising in the Delay Analysis of Broadcast Channels

preprint2020arXivOpen access

Abstract

Consider a broadcast channel with nn users, where different users receive different messages, and suppose that each user has to receive mm packets. A quantity of interest here, introduced by Sharif and Hassibi (2006-7) \cite{Sh}, \cite{S-H}, is the (\emph{packet}) \emph{delay} Dm,nD_{m,n}, namely the number of channel uses required to guarantee that all users will receive mm packets. For the case of a \emph{homogeneous} network, where in each channel use the transmitter chooses a user at random, i.e. with probability 1/n1/n, and sends him//her a packet, the same quantity Dm,nD_{m,n} had already appeared in the \emph{coupon collector} context, in the works of Newman and Shepp (1960) \cite{N-S} and of Erdős and Rényi (1961) \cite{E-R}. A problem of particular interest in wireless communications, related to the delay Dm,nD_{m,n}, is to determine its behavior as nn and mm grow large. Regarding this problem, Sharif and Hassibi \cite{Sh}, \cite{S-H} managed to calculated the asymptotics of the mean value E[Dm,n]\mathbb{E}[D_{m,n}], as n→∞n \to \infty, for the cases (a) m=ln⁡nm = \ln n and (b) m=(ln⁡n)ρm = (\ln n)^ρ, ρ>1ρ> 1. It is remarkable that Erdős and Rényi \cite{E-R} had, also, raised the question of the determination of the asymptotic profile of Dm,nD_{m,n} for large mm and nn (in 1961). And in the 1970's the limiting distribution of Dm,nD_{m,n} for large mm and nn was determined (in great generality) by Ivchenko \cite{I1} and \cite{I2}. In this article we determine the asymptotics of the moments of Dm,nD_{m,n} for large mm and nn. We also derive its limiting distribution in the "supercritical case" where mm grows faster than ln⁡n\ln n and in the "critical case" m∼βln⁡nm \sim β\ln n, by an approach which is different from the one used by Ivchenko.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.