How to calculate probability of observing a value given a permutation distribution? I have a single observation with value $x = 0.5$ that comes out from a complicated computational process. I would like to know what is the probability to observe such value by chance.
To attempt to answer the question, I have ran the computational process with random input values for few thousand times. I get a distribution that is about normal, has mean very close to zero, and a standard deviation around 0.09.
Intuitively, it looks like the chance of observing 0.5 by chance is very little. However, how do I turn this into an actual statistical test?
 A: This is quite straightforward, there is no need to infer a distribution under the Null Hypothesis. Your p-value is just the number of times $x_{permuted}$ get superior or equal to $0.5$, divided by the number of permutations made.
This fits the definition of the p-value: "If H0 is true and a new sample is drawn, what is the probability to get at least such extreme results ?"
Maybe you mixed things up with the Bootstrap procedure which is generally done to estimate the "real" distribution of your statistic of interest. 
I don't say your approach is completely wrong, if your distribution looks like normal, you could eventually do a z-test, and it should give a quite reliable p-value. But I think the spirit of the permutation test is just to count how often you indeed get equal or more extreme results because you have a direct access to it, whatever the real distribution of $x_{permuted}$ is.    
For the sake of the comparison it would be interesting that you give how often $x_{permuted}$ get superior or equal to $0.5$ in your data set, we could compare it with what would give a 1-tailed z-test.
