  In this paper, we develop an analytical framework for the initial access
(a.k.a. Base Station (BS) discovery) in a millimeter-wave (mm-wave)
communication system and propose an effective strategy for transmitting the
Reference Signals (RSs) used for BS discovery. Specifically, by formulating the
problem of BS discovery at User Equipments (UEs) as hypothesis tests, we derive
a detector based on the Generalised Likelihood Ratio Test (GLRT) and
characterise the statistical behaviour of the detector. The theoretical results
obtained allow analysis of the impact of key system parameters on the
performance of BS discovery, and show that RS transmission with narrow beams
may not be helpful in improving the overall BS discovery performance due to the
cost of spatial scanning. Using the method of large deviations, we identify the
desirable beam pattern that minimises the average miss-discovery probability of
UEs within a targeted detectable region. We then propose to transmit the RS
with sequential scanning, using a pre-designed codebook with narrow and/or wide
beams to approximate the desirable patterns. The proposed design allows
flexible choices of the codebook sizes and the associated beam widths to better
approximate the desirable patterns. Numerical results demonstrate the
effectiveness of the proposed method.
