Developing an efficient spectrum access policy enables cognitive radios to dramatically increase spectrum utilization while assuring predetermined quality of service levels for the primary users. In this letter, modeling, performance analysis, and optimization of a distributed secondary network with random sensing order policy are studied. Specifically, the secondary users create a random order of the available channels to sense and find a transmission opportunity in a distributed manner. For this network, the average throughputs of the secondary users and average interference level between the secondary and primary users are evaluated by a new Markov model. Then, a maximization of the secondary network performance in terms of throughput while keeping under control the average interference is proposed. Then, a simple and practical adaptive algorithm is developed to optimize the network in a distributed manner. Interestingly, the proposed algorithm follows the variations of the wireless channels in non-stationary conditions and besides having substantially lower computational cost, it outperforms static brute force optimization. Finally, numerical results are provided to demonstrate the efficiencies of the proposed schemes. It is shown that fully distributed algorithms can achieve substantial performance improvements in cognitive radio networks without the need of centralized management or message passing among the users.