  We introduce a system of monadic affine sized types, which substantially
generalise usual sized types, and allows this way to capture probabilistic
higher-order programs which terminate almost surely. Going beyond plain, strong
normalisation without losing soundness turns out to be a hard task, which
cannot be accomplished without a richer, quantitative notion of types, but also
without imposing some affinity constraints. The proposed type system is
powerful enough to type classic examples of probabilistically terminating
programs such as random walks. The way typable programs are proved to be almost
surely terminating is based on reducibility, but requires a substantial
adaptation of the technique.
