The ability of living cells to maintain an inheritable memory of their gene-expression state is key to cellular differentiation. Bacterial lysogeny serves as a simple paradigm for long-term cellular memory. In this study, we address the following question: in the absence of external perturbation, how long will a cell stay in the lysogenic state before spontaneously switching away from that state? We show by direct measurement that lysogen stability exhibits a simple exponential dependence on the frequency of activity bursts from the fate-determining gene, cI. We quantify these gene-activity bursts using single-molecule-resolution mRNA measurements in individual cells, analyzed using a stochastic mathematical model of the gene-network kinetics. The quantitative relation between stability and gene activity is independent of the fine details of gene regulation, suggesting that a quantitative prediction of cell-state stability may also be possible in more complex systems.