I'm just now learning about all this (I'd heard about stores tracking customers, but thought it only worked with Wifi enabled), but it seems many Android phones don't actually do randomization, and it can be easily fingerprinted even if they do.
From a 2017 paper, https://arxiv.org/abs/1703.02874v1
> First, we show that devices commonly make improper use of randomization by sending wireless frames with the true, global address when they should be using a randomized address. We move on to extend the passive identification techniques of Vanhoef et al. to effectively defeat randomization in ~96% of Android phones. Finally, we show a method that can be used to track 100% of devices using randomization, regardless of manufacturer, by exploiting a previously unknown flaw in the way existing wireless chipsets handle low-level control frames.
and near the end of section 4.2
> Therefore we posit that much less than ∼50% of devices conduct randomization.