Comparing and contrasting, p-values, significance levels and type I error I was wondering if anybody could give a concise rundown as to the definitions and uses of p-values, significance level and type I error.
I understand that p-values are defined as "the probability of obtaining a test statistic at least as extreme as the one we actually observed", while a significance level is just an arbitrary cutoff value to gauge if the p-value is significant or not. Type I error is the error of rejected a null hypothesis that was true. However, I am unsure regarding the difference between significance level and the type I error, are they not the same concept?
For example, assume a very simple experiment where I flip a coin 1000 times and count the number of times it lands on 'heads'. My null hypothesis, H0, is that heads = 500 (unbiased coin). I then set my significance level at alpha = 0.05.
I flip the coin 1000 times and then I calculate the p-value, if the p-value is > 0.05 then I fail to reject the null hypothesis and if the p-value is < 0.05 then I reject the null hypothesis.
Now if I did this experiment repeatedly, each time calculating the p-value and either rejecting or failing to reject the null hypothesis and keeping a count of how many I rejected/failed to reject, then I would end up rejecting 5% of null hypotheses which were in actuality true, is that correct? This is the definition of type I error. Therefore, the significance level in Fisher significance testing is essentially the type I error from Neyman-Pearson hypothesis testing if you performed repeated experiments.
Now as for p-values, if I had gotten a p-value of 0.06 from my last experiment and I did multiple experiments and counted all the ones that I got a p-value from 0 to 0.06, then would I also not have a 6% chance of rejecting a true null hypothesis?
 A: The question looks simple, but your reflection around it shows that it is not that simple.
Actually, p-values are a relatively late addition to the theory of statistics. Computing a p-value without a computer is very tedious; this is why the only way to perform a statistical test until recently was to use tables of statistical tests, as I explain in this blog post. Because those tables were computed for fixed $\alpha$ levels (typically 0.05, 0.01 and 0.001) you could only perform a test with those levels.
Computers made those tables useless, but the logic of testing is still the same. You should:


*

*Formulate a null hypothesis.

*Formulate an alternative hypothesis.

*Decide a maximum type I error (the probability of falsely rejecting the null hypothesis) error you are ready to accept.

*Design a rejection region. The probability that the test statistic falls in the rejection region given that the null hypothesis is your level $\alpha$. As @MånsT explains, this should be no smaller than your acceptable type I error, and in many cases use asymptotic approximations.

*Carry out the random experiment, compute the test statistic and see whether it falls in the rejection region.


In theory, there is a strict equivalence between the events "the statistic falls in the rejection region" and "the p-value is less than $\alpha$", which is why it is felt that you can report the p-value instead. In practice, it allows you to skip step 3. and evaluate the type I error after the test is done.
To come back to your post, the statement of the null hypothesis is incorrect. The null hypothesis is that the probability of flipping a head is $1/2$ (the null hypothesis cannot pertain to the results of the random experiment).
If you repeat the experiment again and again with a threshold p-value of 0.05, yes, you should have approximately 5% rejection. And if you set a p-value cut-off of 0.06, you should end up with roughly 6% rejection. More generally, for continuous tests, by definition of the p-value $p$
$$ Prob(p < x) = x, \, (0 < x < 1), $$
which is only approximately true for discrete tests.
Here is some R code that I hope can clarify this a bit. The binomial test is relatively slow, so I do only 10,000 random experiments in which I flip 1000 coins. I perform a binomial test and collect the 10,000 p-values.
set.seed(123)
# Generate 10,000 random experiments of each 1000 coin flipping
rexperiments <- rbinom(n=10000, size=1000, prob=0.5)
all_p_values <- rep(NA, 10000)
for (i in 1:10000) {
    all_p_values[i] <- binom.test(rexperiments[i], 1000)$p.value
}
# Plot the cumulative density of p-values.
plot(ecdf(all_p_values))
# How many are less than 0.05?
mean(all_p_values < 0.05)
# [1] 0.0425
# How many are less than 0.06?
mean(all_p_values < 0.06)
# 0.0491

You can see that the proportions are not exact, because the sample size is not infinite and the test is discrete, but there is still an increase of roughly 1% between the two.
A: The concepts are indeed intimately linked to each other.
The significance level is the probability of a type I error, or rather, the presumed probability of such an event.  ${\rm P}({\rm type~I~error})= \alpha$ can generally only be obtained when working with continuous distributions, so in classic test theory a test is said to have significance level $\alpha$ if ${\rm P}({\rm type~I~error})\leq \alpha$, meaning that the probability of a type I error is bounded by $\alpha$. However, tests that use approximations of one kind or another actually tend to have ${\rm P}({\rm type~I~error})\approx \alpha$, in which case the probability of a type I error can be larger than the nominal $\alpha$.
The p-value is the lowest significance level at which the null hypothesis would be rejected. Thus it tells us "how significant" the result is.
A: You are getting good answers here from @MansT & @gui11aume (+1 to each). Let me see if I can get more explicitly at something in both of their answers.  
When working with discrete data, there are only certain p-values possible, and the problem is worse with fewer possibilities / smaller data sets.  For example, imagine flipping a coin $n$ times.  The probability of getting a particular number of heads, $k$, is:
$$
p(k)=\frac{n!}{k!(n-k)!}p^k(1-p)^{n-k}
$$
Let's say a researcher want's to test a given coin (which actually is fair) for fairness by flipping it 10 times and recording the number of heads.  That is, the null hypothesis is true here.  Our researcher sets $\alpha=.05$, by convention and because that's what's necessary for acceptance by the larger community. Now, ignoring the conventional alpha for a moment, let's consider the 2-tailed p-values (type I error rates) that are possible in this situation:  
number of heads:           0    1    2    3    4    5    6    7    8    9   10
individual probability:  .001 .010 .044 .117 .205 .246 .205 .117 .044 .010 .001
type I error rate:       .002 .021 .109 .344 .754   1  .754 .344 .109 .021 .002

What this demonstrates is that using $\alpha=.05$ will lead to a long-run 2-tailed type I error rate of $.021$.  So this is clearly a case where $\alpha\ne\text{type I error}$, however, if $\alpha$ were set to one of the above values (instead of $.05$) then the significance level would equal the type I error rate.  Despite that problem, the p-value does equal the type I error rate in this case.  Note that there is no issue here with a mismatch between a discrete inferential statistic and a continuous reference distribution, because I used the exact binomial probabilities.  Note further that situations like this have prompted the development of the mid p-value to help minimize the discrepancy between the p-value and the significance level.
There can be cases where the calculated p-value does not equal the long-run type I error rate, in addition to the fact that the type I error rate doesn't necessarily equal the significance level.  Consider a 2x2 contingency table with these observed counts:  
     col1 col2
row1   2    4   
row2   4    2

Now, how should I calculate the p-value for the independence of the rows and columns?  There are many options (which I discuss here).  I will start by calculating the $\chi^2$ statistic and comparing it to it's reference distribution; that yields $\chi^2_{1}=1.3, p=.248$.  The $\chi^2$ reference distribution is continuous, though, and so only an approximation to how this particular (discrete) $\chi^2$ statistic will behave.  We can use Fisher's exact test to determine the true type I error rate; then I get $p=.5671$.  When the p-value is calculated this way, it does equal the type I error rate, although we still have the question of whether one of the possible p-values is exactly 5%.  Let me admit that I cheated a little, if I had used Yates's correction for continuity, I would have gotten a better approximation of the true type I error rate, but it still wouldn't have been quite right ($.5637\ne .5671$).  
Thus, the issues here are that, with discrete data:  


*

*your preferred significance level may not be one of the possible type I error rates, &  

*using (conventional) approximations to continuous statistics will yield inaccurate calculated p-values.  


These problems are exacerbated the smaller your $N$.  So far as I know, these problems don't exist with continuous data.  
(Although the question doesn't ask about solutions to these problems) there are there are things that mitigate these issues:  


*

*larger $N$ means more possible values, making things more continuous-ish,  

*there are often corrections (such as Yates's correction for continuity) that will bring calculated values closer to correct values,  

*exact tests (if tractable, i.e., if $N$ is small enough) will yield correct p-values  

*the mid p-value offers the possibility of getting your type I error rate closer to your chosen confidence level,

*you can explicitly use one of the type I error rates that exist (or note what it would be).  

A: Summary. Significance level is the approximately same as the probability of getting a Type I errors for discrete distributions. We will show below with basic probability and empirical validation.
-- And they're probably exactly the same for continuous distribution, although I didn't do careful math proof for it.
Theory
Definitions

*

*H0 = Null hypothesis

*$\alpha$ = significance level. Warning: I'll use 'a' below as well.

*P-value (of a sample) = P(observe sample and its extremer versions | H0)

The claim to verify is:
P(Type I error if we use $\alpha$ as p-value threshold) = $\alpha$. Let's see if that is true.
Derivation
P(Type I error)
= P(reject H0 | H0)
= P(p-value < a| H0)

Let's consider this final term. p-value | H0 is a random variable (let's call it X) whose...

*

*events are samples from H0. Let the sample be called $s$.

*value is P(s or its extremer versions | H0) (the definition of p-value), and...

*the associated probability of this event is P(s | H0) (the probability that you get this p-value associated with a sample is the probability that you get this sample)

Let's go back to the derivation.
P(Type I error)
= P(reject H0 | H0)
= P(p-value < a| H0)
= P(X < a)
= Sum_{s such that P(s or its extremer versions | H0) < a} P(s | H0)
# Let's also focus on a binomial random variable B for H0. 
= Sum_{s such that P(B >= s) < a} P(B = s)
= P(B >= s')
  where s' = the smallest s such that P(B >= s) < a
           = the s that makes P(B >= s) as close as possible to a
~ a

Hooray! We showed that P(Type I error) ~ a, and it's an underestimate for a discrete distribution.
Empirical validation
Let's test it against @gui11aume's setup! We will do it in python, but with n = 100,000 instead.
import numpy as np
import scipy.stats as stats

np.random.seed(100)

n = 100000
rexperiments = np.random.binomial(1000, 0.5, n)
all_p_values = np.empty(n)
for i in range(n):
    all_p_values[i] = stats.binom_test(rexperiments[i], 1000, 0.5)

print("Mean of all_p_values less than 0.05:", np.mean(all_p_values < 0.05))
# 0.04588
print("Mean of all_p_values less than 0.06:", np.mean(all_p_values < 0.06))
# 0.05321

$\alpha = 0.05$. s' = the smallest s such that P(B >= s) < a. S' = 527 according to wolframalpha. P(Type I error) = P(B >= 527) = ~0.047, v.s. the empirical 0.04588
$\alpha = 0.06$. P(Type I error) = P(B >= 526) ~ 0.053 v.s. the empirical 0.05321
Close enough!
