The problem of the release of anonymized microdata is an important topic in the fields of statistical disclosure control (SDC) and privacy preserving data publishing (PPDP), and yet it remains sufficiently unsolved. In these research fields, k-anonymity has been widely studied as an anonymity notion for mainly deterministic anonymization algorithms, and some probabilistic relaxations have been developed. However, they are not sufficient due to their limitations, i.e., being weaker than or incomparable to the original k-anonymity, or requiring strong parametric assumptions. In this paper, we propose Pk-anonymity, a new probabilistic k-anonymity. It is proven that Pk-anonymity is a mathematical extension of k-anonymity rather than a relaxation, and requires no parametric assumptions. These properties have a significant meaning in the viewpoint that it enables us to compare privacy levels of probabilistic microdata release algorithms with deterministic ones. We then apply Pk-anonymity to the post randomization method (PRAM), which is an SDC algorithm based on randomization. PRAM is proven to satisfy Pk-anonymity in a controlled way, i.e., one can control PRAM's parameter so that Pk-anonymity is satisfied.