Why is radioactive decay a stochastic process?
Its quantum mechanics which gives this stochastic behavior to it.
Radioactive decay is nothing but decay of unstable nuclei which give out streams of nucleons like alpha particles, neutrons etc.
Consider a hill and a ball rolling upwards with energy not enough to climb it, one would classically expect that there is no way that the ball is found on the other side, and its explanation is pretty intuitive , the ball just doesn't have enough energy to do that and one cannot break the conservation of energy.
Now consider a quantum particle, it too has a hill to climb, this need not necessarily mean a physical hill, but any potential which prevents it from going on to the other side, this is what physicists call a finite potential barrier. Now when one does the same analysis with quantum particles according to quantum rules (Schrodinger equation etc.) We find a bizarre result that there is non zero probability that the particle even without enough energy can cross the finite barrier!
This what is called as Quantum Tunneling, that quantum particles can in principle found on the other side of a potential barrier even though conventional energy conservation disallows it.
The nucleus is also a potential barrier( In this case the barrier is because of forces called nuclear forces) and the nucleons it ejects are quantum particles and they too have a finite probability of crossing that barrier! and that is exactly what decay is this random probabilistic ejection of quantum particles who managed to climb that barrier!
I know it sounds absurd but yet that's the way it is, it is this intrinsic probabilistic nature of Quantum Mechanics that is the sole cause of the radioactive process being stochastic. We can on whole say how many particles are expected to decay through these probabilistic calculations and not which particle will decay when Quantum mechanics gives no information about it!
So in essence every nucleus should decay and indeed theoretically every nucleus does decay but some of them have so large a half time that is safe to assume they don't decay at all, and that is because probability that the quantum particle crosses the barrier depends on the height of the barrier and the width of it for stable nuclei this height is really large hence making them stable , where as for unstable,these are just enough to let particles jump across hence making them unstable.
In essence the stochastic nature is purely a quantum effect and one of the most quantum effects namely Quantum Tunneling.
PS: The answer to the paradox is in the Energy Time Uncertainty Principle, I suggest that you take a look at it.