  We obtain an exact analytic expression for the average distribution, in the
thermodynamic limit, of overlaps between two copies of the same random energy
model (REM) at different temperatures. We quantify the non-self averaging
effects and provide an exact approach to the computation of the fluctuations in
the distribution of overlaps in the thermodynamic limit. We show that the
overlap probabilities satisfy recurrence relations that generalise
Ghirlanda-Guerra identities to two temperatures.
  We also analyse the two temperature REM using the replica method. The replica
expressions for the overlap probabilities satisfy the same recurrence relations
as the exact form. We show how a generalisation of Parisi's replica symmetry
breaking ansatz is consistent with our replica expressions. A crucial aspect to
this generalisation is that we must allow for fluctuations in the replica block
sizes even in the thermodynamic limit. This contrasts with the single
temperature case where the extremal condition leads to a fixed block size in
the thermodynamic limit. Finally, we analyse the fluctuations of the block
sizes in our generalised Parisi ansatz and show that in general they may have a
negative variance.
