function tsamps = disc_acc_rej(p,n)
% DISC_ACC_REJ - the discrete version of the acceptance rejection method for generating random variables
% 
% Input:
%   n: we generate a [1,n] array of random variables.
%
% Written by:
% -- 
% John L. Weatherwax                2008-02-20
% 
% email: wax@alum.mit.edu
% 
% Please send comments and especially bug reports to the
% above email address.
% 
%-----

% the number of discrete random variables
nDisc = length(p); 

% the discrete uniform distribution will have probabilities given by 
q = 1/nDisc;

% Find the constant "c" such that p_i \le c q_i , where q_i=q is the discrete uniform prob. distribution
c = max( p )/q; 

% generate enough samples until we get "n" discrete random variables: 
tsamps = zeros(1,n); indx=1;
while( indx<=n )
  nu      = ceil(nDisc*rand);  % <- generate a discrete uniform random sample with in [1,nDisc]
  theFrac = p(nu)/(c*q);
  if( rand <= theFrac )
    tsamps(indx)=nu;
    indx=indx+1;
  end
end