function [yhat] = k_nn(k,Y,X,w);

% k-nearest neighbor routine
% calculates k-nearest neighbor estimate of E[y|x] at each point 
% given in the vector w.
%
% if there are multiple neighbors at the same distance, picks k
% of them at random 
%
% k: a positive integer, k<length(Y)
% Y: an n x 1 vector
% X: an n x 1 vector
% w: a  j x 1 vector, j not necessarily equal to n
% yhat: a j x 1 vector 
% note this program doesn't check to make sure inputs fit these 
% requirements

n = length(Y);
j = length(w);
yhat=NaN*ones(j,1);

for i=1:j,
   % first, randomize order of the observations
   [z,index_random] = sort(rand(n,1));
   Yi = Y(index_random);
   Xi = X(index_random);
   
   % calculate distance
   distance = abs( Xi-w(i) );

   % calculate an index based on distance to w(i)
   [zz,index_distance]=sort(distance);
   Y_by_distance = Yi(index_distance);
   
   yhat(i) = mean(Y_by_distance(1:k));
      
end;