public DependencyInstance randomWalkSampling(DependencyInstance inst,
    		LocalFeatureData lfd, boolean addLoss)
    {
        //int cnt = 0;
    	int len = inst.length;
    	
		DependencyInstance predInst = new DependencyInstance(inst);
		predInst.heads = new int[len];
		predInst.deplbids = new int[len];
        
        double[] score = new double[len];
        int[] depList = new int[len];
        int size = 0;

    	boolean[] inTree = new boolean[len];
    	inTree[0] = true;
    	for (int i = 0; i < len; i++) {
    		predInst.heads[i] = -1;
    	}
    	
    	for (int i = 1; i < len; i++) {
    		int curr = i;
    		while (!inTree[curr]) {
    			// sample new head 
                size = 0;

    			for (int candH = 0; candH < len; candH++) {
    				if (candH == curr || lfd.isPruned(candH, curr))
    					continue;
    				
    				double s = lfd.getArcScore(candH, curr);
    				
    				if (addLoss) {
    					  if (candH != inst.heads[curr])
    						s += 1.0;
    				}
                    score[size] = s;
                    depList[size] = candH;
                    ++size;
    			}

    			int sample = samplePoint(score, size, r);
    			predInst.heads[curr] = depList[sample];
    			curr = predInst.heads[curr];
    		}
    		curr = i;
    		while (!inTree[curr]) {
    			inTree[curr] = true;
    			curr = predInst.heads[curr]; 
    		}
    	}
    	
    	return predInst;
    }