The number of tries needed to get N zero bits of POW is geometrically distributed with
p = 1 / (2^N)
The expected number of tries is
2^N
(on average you'll need to try 256 different nonces to get 8 bits of POW, an event ID starting with `00`)
The variance on the number of tries is
2^(2N) (1 - 1/2^N)
which, conveniently, makes for a standard deviation of about
2^N
for large N
All that to say, setting POW to 25 in gossip was usually fine, but the occasional note took a painful amount of time.