What is the mathematical difference between random- and fixed-effects? I have found a lot on the internet regarding the interpretation of random- and fixed-effects. However I could not get a source pinning down the following:
What is the mathematical difference between random- and fixed-effects?
By that I mean the mathematical formulation of the model and the way parameters are estimated.
 A: The simplest model with random effects is the one-way ANOVA model with random effects, given by observations $y_{ij}$ with distributional assumptions: $$(y_{ij} \mid \mu_i) \sim_{\text{iid}} {\cal N}(\mu_i, \sigma^2_w), \quad j=1,\ldots,J, 
\qquad 
\mu_i \sim_{\text{iid}} {\cal N}(\mu, \sigma^2_b), \quad i=1,\ldots,I.$$
Here the random effects are the $\mu_i$. They are random variables, whereas they are fixed numbers in the ANOVA model with fixed effects. 
For example each of three technicians $i=1,2,3$ in a laboratory records a series of measurements, and $y_{ij}$ is the $j$-th measurement of technician $i$. Call $\mu_i$ the "true mean value" of the series generated by technician $i$;  this is a slightly artificial parameter, you can see $\mu_i$ as the mean value that technician $i$ would have been obtained if he/she had recorded a huge series of measurements.
If you are interested in evaluating $\mu_1$, $\mu_2$, $\mu_3$ (for example in order to assess the bias between operators), then you have to use the ANOVA model with fixed effects. 
You have to use the ANOVA model with random effects when you are interested in the variances $\sigma^2_w$ and $\sigma^2_b$ defining the model, and the total variance $\sigma^2_b+\sigma^2_w$ (see below). The variance $\sigma^2_w$ is the variance of the recordings generated by one technician (it is assumed to be the same for all technicians), and $\sigma^2_b$ is called the between-technicians variance. Maybe ideally, the technicians should be selected at random.
This model reflects the decomposition of variance formula for a data sample :

Total variance = variance of means $+$ means of intra-variances
which is reflected by the ANOVA model with random effects:

Indeed, the distribution of $y_{ij}$ is defined by its conditional distribution $(y_{ij})$ given $\mu_i$ and by the distribution of $\mu_i$. If one computes the "unconditional" distribution of $y_{ij}$ then we find $\boxed{y_{ij} \sim {\cal N}(\mu, \sigma^2_b+\sigma^2_w)}$.
See slide 24 and slide 25 here for better pictures (you have to save the pdf file to appreciate the overlays, don't watch the online version).
A: In econ land, such effects are individual-specific intercepts (or constants) that are unobserved, but can be estimated using panel data (repeated observation on the same units over time). The fixed effects estimation method allows for correlation between the unit-specific intercepts and the independent explanatory variables. The random effects does not. The cost of using the more flexible fixed effects is that you cannot estimate the coefficient on variables that are time-invariant (like gender, religion, or race).
N.B. Other fields have their own terminology, which can be rather confusing. 
A: In a standard software package (e.g. R's lmer), the basic difference is:


*

*fixed effects are estimated by maximum likelihood (least squares for a linear model)

*random effects are estimated by empirical Bayes (least squares with some shrinkage for a linear model, where the shrinkage parameter is chosen by maximum likelihood)


If you're being Bayesian (e.g. WinBUGS), then there is no real difference.
A: Basically, what I think is the most distinct difference if you model a factor as random, is that the effects are assumed to be drawn from a common normal distribution.
For example, if you have some sort of model regarding grades and you want to account for your student data coming from different schools and you model school as a random factor this means that you assume that the by school averages are normally distributed. That means two sources of variation are modelling: the in-school variability of student grades and the between school variability. 
This results in something called partial pooling. Consider two extremes:


*

*School does not have any effect (between school variability is zero). In this case a linear model which does not account for school would be optimal.

*School variability is larger than student variability. Then you basically need to work on the school level instead of the students level (less # samples). This is basically the model where you account for school using fixed effects. This can be problematic if you have few samples per school.


By estimating the variability at both levels the mixed model makes a smart compromise between these two approaches. Especially if you have a not so large #students per school this means that you will get shrinkage of the effects for the individual schools as estimated by model 2 towards the overall mean of model 1. 
That is because the models says that if you have one school with two students included which is better than what is "normal" for the population of schools then it is likely that part of this effect is explained by the school having been lucky in the choice of the two students looked at. It does not make this blindly, it does so depending on the estimate of the within school variability. This also means that effect levels with fewer samples are more strongly pulled toward the overall mean than large schools. 
The important thing is that you need exchangeability on the levels of the random factor. That means in this case that the schools are (from your knowledge) exchangeable and you know nothing which makes them distinct (other than some sort of ID). If you have additional information you can include this as an additional factor, it is enough that the schools are exchangeable conditional on the other information accounted for. 
For example, it would make sense to assume that 30 year old adults living in New York are exchangeable conditional on gender. If you have more information (age, ethnicity, education) it would make sense to include that information as well.
OTH if you have study with one control group and three wildly different disease groups it does not make sense to model group as random since specific disease are not exchangeable. However, many people like the shrinkage effect so well that they would still argue for a random effects model but that's another story.  
I notice I didn't get too much into the mathematics, but basically the difference is that the random effects model estimated a normally distributed error both on the level of schools and on the level of students while the fixed effect model has the error just on the level of students. Especially this means that each school has it's own level that is not connected to the other levels by a common distribution. This also means that the fixed model does not allow extrapolating to a student of school not included in the original data while the random effect model does so, with an variability that is the sum of the student level and the school level variability. If you are specifically interested in the likelihood we could work that in.
A: From reading the answers above I guess the major difference is whether we assume a Gaussian for the individual means. Fixed effects don't say much about that assumption because what we are interested is whether A sample differs from B sample (e.g., Are males taller than females?). While if that's not our aim, estimation of individual means can be sometimes meaning less. E.g., 10 people tested in two conditions, and the absolute value of the 20 means are meaning less, because the participants were sampled - what we really interested in is whether the two conditions differ. And then we assume that the individual means are drawn from a Gaussian. And that answers why we should turn to fixed effects when every level is drawn from from the factor - because it is no longer reasonable to assume a hypothetical distribution when the actual distribution is given. I admit that I don't know much about the math behind the calculations.
