But lets see if we can keep things non-linear.    Suppose your BirthdayHash has 32 bits, but your nonce search space only has 16 bits.    You will run out of nonces long before you are able to generate enough birthdays to get very high on the q(n) curve.    I would guess you could tune the parameters in the following way:

Limit the nonce search space such that the expected number of birthday matches is 1.   If this were the actual birthday problem, we would set the nonce nonce search space to ~50 and number of days to 365.  99% of the time you would find 1 match, though sometimes you might find 2 or 0. 

Once all nonces of been searched, you have to start over again.