We consider a wireless downlink communication system with N parallel channels under the following two assumptions: (1) the channels states can be explicitly sensed at a limited rate !s, (2) channels are modeled as i.i.d., ON/OFF Markov chains with stationary distribution ["OFF , "ON]. The goal of this paper is to characterize the fundamental trade-off between system throughput and channel sensing rate !s in the challenging scenario in which N !" and jointly "ON ! 0. To this end, we propose a simple scheduling algorithm that effectively exploits channel memory to maximize the successful transmission probability. We obtain sufficient and necessary conditions to achieve maximum (in order sense) system throughput. Finally, we show the performance of our policy under a non-asymptotic scenario.