Rejection sampling is performed to acquire at least one target language translation for a source language string s in accordance with a phrase-based statistical translation model p(x)=p(t, a|s) where t is a candidate translation, a is a candidate alignment comprising a biphrase sequence generating the candidate translation t, and x is a sequence representing the candidate alignment a. The rejection sampling uses a proposal distribution comprising a weighted finite state automaton (WFSA) q(n) that is refined responsive to rejection of a sample x* obtained in a current iteration of the rejection sampling to generate a refined WFSA q(n+1) for use in a next iteration of the rejection sampling. The refined WFSA q(n+1) is selected to satisfy the criteria p(x)≦q(n+1)(x)≦q(n)(x) for all x∈X and q(n+1)(x*)