You are given a directed acyclic graph G = (V, E) with a source nodes e V and a sink node te V. The graph is a lattice: s is the only node with no incoming edges, and t is the only node with no outgoing edges. You wish to use Gibbs sampling to sample from all paths from s to t with uniform probability. Your advisor proposes the following Gibbs sampling algorithm: assign a variable z, to each vertex v. The values of zy range over vertices that are reachable in one step from v: {u : (v, u) E E}. Any assignment to all variables zy specifies a path from s to t: the path is determined by starting at s and following the sequence s, zg, Zz,, .. .. The algorithm iterates over vertices v and resamples each variable zy uniformly at random. We wish to show that the algorithm converges to a uniform distribution over all paths from s to t. EITHER Show that the algorithm above converges to the correct distribution by showing that this distribution satisfies detailed balance, and that the chain is aperiodic and irreducible, OR Provide an example of a graph for which the algorithm above does not converge to the correct distribution. You are given a directed acyclic graph G = (V, E) with a source nodes e V and a sink node te V. The graph is a lattice: s is the only node with no incoming edges, and t is the only node with no outgoing edges. You wish to use Gibbs sampling to sample from all paths from s to t with uniform probability. Your advisor proposes the following Gibbs sampling algorithm: assign a variable z, to each vertex v. The values of zy range over vertices that are reachable in one step from v: {u : (v, u) E E}. Any assignment to all variables zy specifies a path from s to t: the path is determined by starting at s and following the sequence s, zg, Zz,, .. .. The algorithm iterates over vertices v and resamples each variable zy uniformly at random. We wish to show that the algorithm converges to a uniform distribution over all paths from s to t. EITHER Show that the algorithm above converges to the correct distribution by showing that this distribution satisfies detailed balance, and that the chain is aperiodic and irreducible, OR Provide an example of a graph for which the algorithm above does not converge to the correct distribution