Constructing a tridiagonal Markov Chain given a desired distribution Given a desired distribution over a set of finite states, I wish to construct a tridiagonal Markov chain that would have a stationary distribution same as the desired distribution.
The reason I want to do this is as follows. I have a linear sequence of blocks that an agent can traverse. Each time, the agent can choose to stay at the current block, move forward one block, or move backward one block. However, I also have a target distribution such that over time, I want the frequency that each block gets visited to be similar to the target distribution.
I personally don't know any existing methods/tools that could easily solve this due to my limited knowledge in statistics. I'd appreciate it if anyone can provide some advice on how I might be able to approach this problem.
 A: A stationary distribution $x=(x_1, x_2, \ldots, x_n)$ imposes a set of $n$ linear relations on the $2(n-1)$-dimensional manifold of tridiagonal transition matrices $\{\mathbb{P}\}$ via the defining equation
$$x\mathbb{P} = x.$$
There is one linear relation among these constraints.  The general solution of (up to) $2(n-1) - (n-1) = n-1$ dimensions therefore can be parameterized by $n-1$ real values $\lambda_i$.  We only need to ensure that all entries in the transition matrix are non-negative.  This works out to the set of inequalities
$$\eqalign{
0 \le &\lambda_1 x_2 & &\le 1 \\
0 \le &\lambda_1 x_1 &+ \lambda_2 x_3 &\le 1 \\
0 \le &\lambda_2 x_2 &+ \lambda_3 x_4 &\le 1 \\
0 \le & &\cdots &\le 1 \\
0 \le &\lambda_{n-2} x_{n-2} &+ \lambda_{n-1} x_n &\le 1 \\
0 \le &\lambda_{n-1} x_{n-1}& &\le 1
}$$
which can always be satisfied for sufficiently small $\lambda_i$, because all the $x_i$ are non-negative.
As an example to show the pattern, here is the general solution for $n=5$:
$$\left(
\begin{array}{ccccc}
 1-x_2 \lambda _1 & x_2 \lambda _1 & 0 & 0 & 0 \\
 x_1 \lambda _1 & 1-x_1 \lambda _1-x_3 \lambda _2 & x_3 \lambda _2 & 0 & 0 \\
 0 & x_2 \lambda _2 & 1-x_2 \lambda _2-x_4 \lambda _3 & x_4 \lambda _3 & 0 \\
 0 & 0 & x_3 \lambda _3 & 1-x_3 \lambda _3-x_5 \lambda _4 & x_5 \lambda _4 \\
 0 & 0 & 0 & x_4 \lambda _4 & 1-x_4 \lambda _4
\end{array}
\right)$$
It is obvious that this is a transition matrix because (a) the inequalities imply all coefficients are non-negative and (b) all row sums equal $1$.  As a check, notice that left-multiplying this matrix by $x$ gives $x$ itself, showing that $x$ indeed is a stationary distribution.  It is the most general solution because it depends (linearly) on $n-1$ independent parameters.  You therefore have freedom to impose additional requirements on $\mathbb{P}$ if you like.
