The birthday paradox speaks to the probability of having a collision, though - in other words, if you randomly try wallets, the probability that you hit one aga

The birthday paradox speaks to the probability of having a collision, though - in other words, if you randomly try wallets, the probability that you hit one again that you've tried already. That probability is higher than the probability of hitting a non-zero wallet, once you've tried more wallets than there are non-zero wallets. The birthday paradox says that you need to try sqrt(N) before you have a collision, while here we still need to hit N/k (where k is the number of non-zero wallets) before we find a non-zero wallet, and the latter number is much bigger than the former.