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.