Random access protocols have been the mechanism of choice for most WLANs, thanks to their simplicity and distributed nature. Nevertheless, these advantages come at the price of sub-optimal channel utilization because of empty slots and collisions. In previous random access protocols, the stations transmit on the channel without any clue of other stations intentions to transmit. In this article we provide a framework to study the efficiency of channel access protocols. This framework is used to analyze the efficiency of the Binary Exponential Backoff mechanism and the maximum achievable efficiency that can be obtained from any completely random access protocol. Then we propose Learning-BEB (L-BEB). L-BEB is exactly the same as legacy BEB, with one exception: L-BEB chooses a deterministic backoff value after a successful transmission. We call this value the virtual frame size (V ). This subtle modification significantly reduces the number of collisions. It can be observed that, as the system runs, the number of collisions is progressively reduced. Thus we conclude that the system learns. Further, if the number of contending stations is equal or lower than V and all stations consecutively successfully transmit, collisions disappear. This collision-free operation is maintained until a new station is activated and joins the contention. L-BEB pushes the system performance beyond the upper bound inherent to completely-random access mechanisms. Moreover, L-BEB does not introduce any additional complexity to the algorithms currently in use in WLANs. All the claims in the paper are supported by extensive simulation results.