Generate trajectories using the FFBS (forward filtering backward
        sampling) algorithm. 

        Arguments
        ---------
        M: int
            number of trajectories we want to generate
        linear_cost: bool 
            if set to True, the O(N) version is used, see below. 

        return_ar: bool (default=False)
            if set to True, change the output, see below. 
        
        Returns
        -------
        paths: a list of ndarrays
            paths[t][n] is component t of trajectory m. 
        ar: float
            the overall acceptance rate of the rejection procedure

        Notes
        -----

        1. if ``linear_cost=False``, complexity is O(TMN); i.e. O(TN^2) for M=N;
           if ``linear_cost=True``, complexity is O(T(M+N)), i.e. O(TN) for M=N.
           This requires that model has method `upper_bound_trans`, which
           provides the log of a constant C_t such that
           :math:`p_t(x_t|x_{t-1}) \leq C_t`. 

        2. main output is ``paths``, a list of T arrays such that
           ``paths[t][m]`` is component t of trajectory m.

        3. if ``linear_cost=True`` and ``return_ar=True``, output is tuple
           ``(paths, ar)``, where ``paths`` is as above, and ``ar`` is the overall 
           acceptance rate (of the rejection steps that choose the ancestors);
           otherwise output is simply ``paths``.

def backward_sampling(self, M, linear_cost=False, return_ar=False):
        """Generate trajectories using the FFBS (forward filtering backward
        sampling) algorithm. 

        Arguments
        ---------
        M: int
            number of trajectories we want to generate
        linear_cost: bool 
            if set to True, the O(N) version is used, see below. 

        return_ar: bool (default=False)
            if set to True, change the output, see below. 
        
        Returns
        -------
        paths: a list of ndarrays
            paths[t][n] is component t of trajectory m. 
        ar: float
            the overall acceptance rate of the rejection procedure

        Notes
        -----

        1. if ``linear_cost=False``, complexity is O(TMN); i.e. O(TN^2) for M=N;
           if ``linear_cost=True``, complexity is O(T(M+N)), i.e. O(TN) for M=N.
           This requires that model has method `upper_bound_trans`, which
           provides the log of a constant C_t such that
           :math:`p_t(x_t|x_{t-1}) \leq C_t`. 

        2. main output is ``paths``, a list of T arrays such that
           ``paths[t][m]`` is component t of trajectory m.

        3. if ``linear_cost=True`` and ``return_ar=True``, output is tuple
           ``(paths, ar)``, where ``paths`` is as above, and ``ar`` is the overall 
           acceptance rate (of the rejection steps that choose the ancestors);
           otherwise output is simply ``paths``.
        """
        idx = np.empty((self.T, M), dtype=int)
        idx[-1, :] = rs.multinomial(self.wgt[-1].W, M=M)
        if linear_cost:
            ar = self._backward_sampling_ON(M, idx)
        else:
            self._backward_sampling_ON2(M, idx)
        # When M=1, we want a list of states, not a list of arrays containing 
        # one state
        if M == 1:
            idx = idx.squeeze(axis=1)
        paths = [self.X[t][idx[t]] for t in range(self.T)]
        if linear_cost and return_ar:
            return (paths, ar)
        else:
            return paths