How can permutation test be used for assessing the prediction capability of a model? I have a set of real labels $(y_1, y_2, ...,y_n)$ and predictions $(\hat{y}_1, \hat{y}_2, ...,\hat{y}_n)$ produced by my model. My supervisor has told me to assess the significance of the predictions by using a permutation test. 
I'm very new to permutation test and I tried using the code from this site: http://spark.rstudio.com/ahmed/permutation/
What I got was a very high P-value of more than 0.9. I started to wonder if I did something wrong.
How is permutation test used in testing if my prediction results are statistically significant or not?
 A: Here's the general way this sort of thing proceeds. Let there be some statistic of interest, $T$ (which could for example correspond to a measure of association, or of deviation - lack of fit, such as MSE). You also need to figure out for your $T$ whether very large values, very small values or both large and small values correspond to 'better than chance'. For example, small values of MSE are "better", and large values of some measure of association are "better". (In the case of C-index, large is better)
The aim is to check whether the particular set of predictions is "better than random" as measured by the statistic - whether the predictions are more associated with the outcomes than you'd expect if it was just due to randomness, for example.
Call the original statistic computed on your data $T^*$.
1. Repeat m times:
    shuffle (i.e. permute the labels on) the predictions
    compute T(i) (and save into the i-th position of some m-vector)

2. find out where your original T* is in the distribution - specifically, find the 
   proportion of resampled T statistics at least as extreme in the "better" direction, 
   ... but conventionally you should also count the original sample T* in the proportion 
   of "at least as extreme" as your value (both in the numerator and denominator)

That result is an estimated p-value. If $m$ is large, it should be close to the p-value obtained by considering all possible shuffles.
Note that strictly a permutation test is what we call it if we do consider all possible shuffles. If you just sample them with replacement, as here, it's properly called a randomization test.
