In this paper, a power saving scheme is investigated for macrocell-assisted small cell networks in the downlink, in which small cells are selected to stay in sleep or wake-up modes in order to mitigate excessive power consumption and the small cells operating in the sleep mode are eligible to off-load their served users to the macrocell to preserve communications. By taking the dynamics of user arrival into account, we attempt to minimize the average total power consumption of the network, which depends on several network parameters like power consumption of base stations, available bandwidth, user load in the cells, cell size, user rate requirement, rate outage probability and noise power density, while ensuring the average number of dropping off-loaded users to a satisfactory level. The design problem is then formulated as a constrained Markov decision process and solved via linear programming. A randomized strategy is proposed to accomplish the optimal sleep/wake-up policy for small cells. Simulation results confirm the effectiveness of the proposed scheme, as compared with the one without adopting sleep/wake-up mechanisms, and help us to capture the impact of the network parameters on the entire power saving.