function i = walker_sampler ( n, y, a )

%*****************************************************************************80
%
%% walker_sampler() returns a random sample i=1..N with prob X(i).
%
%  Discussion:
%
%    Implementation of algorithm for sampling from a discrete
%    probability N-vector X(1), X(2), ..., X(N).  (N>=1.)
%    Runs on O(1) worst case time per sample,
%    and uses one integer and one real N-element array for storage.
%    Preprocessing consumes O(N) time and temporarily uses one 
%    additional integer array (B(0..N+1)) for bookkeeping. 
%    X(0) and X(N+1) are also used as sentinels in the Build() algorithm.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    11 July 2021
%
%  Author:
%
%    Original C version by Warren Smith.
%    MATLAB version by John Burkardt.
%
%  Reference:
%
%    Warren Smith,
%    How to sample from a probability distribution,
%    April 18, 2002.
%
%  Input:
%
%    integer N, indicates the size of X.
%
%    real Y(0:N+1), the Walker threshold vector.
%
%    integer A(0:N+1), the Walker index vector.
%
%  Output:
%
%    integer I, a sample value between 1 and N,
%    selected according to the probability vector X.
%

% 
%  Let i = random uniform integer from {1,2,...N}  
%
  i = randi ( [ 1, n ], 1 );

  r = rand ( 1, 1 );

  if ( y(i+1) < r )
    i = a(i+1);
  end

  return
end

