def _backward_sampling_ON(self, M, idx):
        """O(N) version of backward sampling.

        not meant to be called directly, see backward_sampling
        """
        nattempts = 0
        for t in reversed(range(self.T - 1)):
            where_rejected = np.arange(M)
            who_rejected = self.X[t + 1][idx[t + 1, :]]
            nrejected = M
            gen = rs.MultinomialQueue(self.wgt[t].W, M=M)
            while nrejected > 0:
                nattempts += nrejected
                nprop = gen.dequeue(nrejected)
                lpr_acc = (self.model.logpt(t + 1, self.X[t][nprop], 
                                            who_rejected)
                           - self.model.upper_bound_trans(t + 1))
                newly_accepted = np.log(random.rand(nrejected)) < lpr_acc
                still_rejected = np.logical_not(newly_accepted)
                idx[t, where_rejected[newly_accepted]] = nprop[newly_accepted]
                where_rejected = where_rejected[still_rejected]
                who_rejected = who_rejected[still_rejected]
                nrejected -= sum(newly_accepted)
        return (M * (self.T - 1)) / nattempts