We propose a new pseudo-random pattern generator for scan circuits. The proposed generator uses Markov sources to capture spatial correlations between consecutive bits inside a scan chain as defined by weight sets generated using a weighted random pattern testing method. The weight set generation is based on the analysis of deterministic test sets. The BIST scheme that uses the proposed pattern generator iteratively modifies the generator behavior to obtain a full fault coverage. Experiments conducted on large benchmark circuitsdemonstrate that the proposed BIST methodology can achieve full fault coverage with a small number of tests and a small hardware overhead.