On probe requests this can be very often(< second or within 50 frames), especially in the case of IOS. On Android MAC randomisation is implemented only on a handful of specific devices and some vendors dont at all.
Mac randomisation is flawed at the least and can still be used to identify an individual in some cases.
The paper below lists techniques explored by the US Navy published in 2017.
https://arxiv.org/pdf/1703.02874.pdf