Efficient design of cognitive radio networks calls for secondary users implementing adaptive resource allocation, which requires knowledge of the channel state information in order to limit interference inflicted to primary users. In this context, the present paper develops stochastic resource allocation algorithms maximizing the sum-rate of secondary users while adhering to "average power" and "probability of interference" constraints. These constraints guarantee that the probability of the secondary network interfering with the primary one stays below a pre-specified level. The optimal schemes turn out to be a function of the quality of the secondary network links, the activity of the primary users, and the associated Lagrange multipliers. The focus is on algorithms that: i) use stochastic approximation tools to estimate the multipliers; and ii) are able to cope with imperfections in the information of the primary network state.