For a research project I'm dealing with a combinatorial problem which I am modeling as a disordered system. For some context, the problem is the TSP, and the disorder enters through the weights on its edges.
Essentially, I'm modelling the edge weights as i.i.d. random variables, and defining a Gibbs measure on the set of TSP tours. I then draw a tour according to this distribution, and consider its length $J$. My goal is to bound $\mathrm{Pr}(J < (1-\epsilon)E(J))$ for $0 < \epsilon < 1$, where $E(\cdot)$ denotes expectation.
This system falls within the domain of quenched disorder, and some nice things can be said about it from that perspective. Of course quenched disorder is pretty hard to deal with, so I would like to consider the disorder as annealed, instead. This is where I start running into problems.
From what I understand (see e.g. this answer) quenched disorder corresponds to a system where the disordered variables are "frozen", i.e. chosen according to some distribution and kept fixed when one defines a Gibbs measure on the system. In contrast, annealed disorder corresponds to the case where the disordered variables are also considered as degrees of freedom, and evolve on the same time scale as the other degrees of freedom.
The other common description of annealed disorder is through the partition function of the system. If $Z(\beta|X)$ is the partition function of a system that depends on disordered variables $X$, then quenched disorder is described by setting the free energy as $-\frac{1}{\beta}E(\ln Z(\beta |X))$, while annealed disorder has it as $-\frac{1}{\beta}\ln E(Z(\beta|X))$.
My first question is: why does this partition function describe the annealed disorder as defined above? I don't understand why taking the expectation of $Z$ corresponds to letting the disorder variables thermally equilibrate. Actually, I'm not even completely sure what it means for the disorder variables to thermally equilibrate. The best explanation I've found is this answer, but I still don't understand one thing there: if the $J_{ij}$ in that answer are treated as degrees of freedom, what is the role of their probability distribution?
Now secondly, in terms of a random experiment, quenched disorder is pretty clear to me:
- Set up a finite set $S$.
- Draw the disordered variables $X$ from some distribution (e.g. in my model, $X = (X_i, \ldots, X_m)$, with $X_i \sim U[0,1]$ for each edge).
- Define a function $f$ on $S$, which depends in addition on the realization of $X$.
- Define a Gibbs measure on $S$ at a finite temperature, using $f$ as the "energy" for each state $s \in S$.
- Draw a state $s$ according to this Gibbs measure.
- Calculate $J = f(s|X)$.
The statistics for $J$ are well-defined, if hard to deal with due to the disorder.
From the intuitive description of annealed disorder as allowing the disordered variables ($X$ above) to equilibrate, I would imagine that an equivalent experiment with annealed disorder would yield smaller results for $J$. This is certainly true in expectation: if we let $Z(\beta|X)$ be the disorder-dependent partition function ($\beta$ being the inverse temperature), it's not too hard to show that $-\partial_\beta E(\ln Z(\beta|X)) \geq - \partial_\beta \ln E(Z(\beta|X))$.
Ideally, letting $I$ denote the outcome of the annealed experiment, I would like to show that $J$ stochastically dominates $I$ (in first order).
My second question is then: does anyone know of a result vaguely in this direction, or failing that, does anyone know of a nice interpretation of the annealed process that is similar to the above, i.e. that can be written in terms of a random experiment? All literature on the topic I've found just gives the physical picture of the two types of disorder, or simply mentions how the two pictures treat the partition function and leaves it at that.
