The effects of bias on sampling algorithms and combinatorial objects

Markov chains are algorithms that can provide critical information from exponentially large sets efficiently through random sampling. These algorithms are ubiquitous across numerous scientific and engineering disciplines, including statistical physics, biology and operations research. In this thesis we solve sampling problems at the interface of theoretical computer science with applied computer science, discrete mathematics, statistical physics, chemistry and economics. A common theme throughout each of these problems is the use of bias. The first problem we study is biased permutations which arise in the context of self-organizing lists. Here we are interested in the mixing time of a Markov chain that performs nearest neighbor transpositions in the non-uniform setting. We are given "positively biased'' probabilities $\{p_{i,j} \geq 1/2 \}$ for all $i < j$ and let $p_{j,i} = 1-p_{i,j}$. In each step, the chain chooses two adjacent elements~$k,$ and~$\ell$ and exchanges their positions with probability $p_{ \ell, k}$. We define two general classes of bias and give the first proofs that the chain is rapidly mixing for both. We also demonstrate that the chain is not always rapidly mixing by constructing an example requiring exponential time to converge to equilibrium. Next we study rectangular dissections of an $n \times n$ lattice region into rectangles of area $n$, where $n=2^k$ for an even integer $k.$ We consider a weighted version of a natural edge flipping Markov chain where, given a parameter $\lambda > 0,$ we would like to generate each rectangular dissection (or dyadic tiling)~$\sigma$ with probability proportional to $\lambda^{|\sigma|},$ where $|\sigma|$ is the total edge length. First we look at the restricted case of dyadic tilings, where each rectangle is required to have the form $R = [s2^{u},(s+1)2^{u}]\times [t2^{v},(t+1)2^{v}],$ where $s, t, u$ and~$v$ are nonnegative integers. Here we show there is a phase transition: when $\lambda 1,$ the mixing time is $\exp(\Omega({n^2}))$. The behavior for general rectangular dissections is more subtle, and we show the chain requires exponential time when $\lambda >1$ and when $\lambda