We address a natural question in average-case complexity: does there exist a language L such that for all easy distributions D the distributional problem ( L D ) is easy on the average while there exists some more hard distribution D such that ( L D ) is hard on the average? We consider two complexity measures of distributions: complexity of sampling and complexity of computing the distribution function. The most interesting measure is the complexity of sampling. We prove that for every a > 0"> b a 0 there exists a language L , an ensemble of distributions D samplable in n log b n steps and a linear-time algorithm A such that for every ensemble of distribution F that samplable in n log a n steps, A correctly decides L on all inputs from 0 1 n except of a set that has infinitely small F -measure, and for every algorithm B there are infinitely many n such that the set of all elements of 0 1 n for which B correctly decides L has infinitely small D -measure.

In case of complexity of computing the distribution function we prove the following tight result: for every 0"> a 0 there exists a language L , an ensemble of polynomial-time computable distributions D , and a linear-time algorithm A such that for every computable in n a steps ensemble of distributions F , A correctly decides L on all inputs from 0 1 n except a set that has F -measure at most 2 − n 2 , and for every algorithm B there are infinitely many n such that the set of all elements of 0 1 n for which B correctly decides L has D -measure at most 2 − n +1 .