# Hit-n-Run Monte Carlo on convex polytope

So, I'm currently trying to implement a MCMC to uniformly sampling hyper-points from the polytope defined as $$\mathbb{K}=\{x\in\mathbb{R}^{n}\;\;\text{s.t.}\;\; A\,x=b \}$$ in the specific case where, given a generic linear transformation $$A\in\mathbb{R}^{m\times n}$$, $$b\equiv0\in\mathbb{R}^m$$ and the boundary conditions $$0\leq x\leq1$$ hold.

Now, although I was able to succesfully perform the simulation (I am using Julia), there are some things I am not quite sure about:

• given the fact that polytopes of this this kind tend to have star-like shapes in higher dimensions, two pre-processing steps are required, before launching the simulation:

1. the first regards the so-called blocked-flux adjustment which consists, quote from the text of the exercise, find fluxes $$i$$ such that $$\max_{x\in K} x_i = \min_{x\in K} x_i = z_i$$ and remove such variables from the system, adjusting the vector $$b$$. Can anyone please explain to me what the heck this means?

2. the second consists in finding an optimal inner point in $$\mathbb{K}$$ as a starting point of the chain, which intuitevely enough has to be located far from the vertexes of the polytope. The text tells me this: it can be done e.g. by computing $$\frac{1}{2n}\sum_{i=1}^n (x^{\min,i} + x^{\max,i})$$ where $$x^{\min,i} \in \arg\min_{x\in K} x_i$$ and $$x^{\max,i} \in \arg\max_{x\in K} x_i$$. Here I just do not understand the notation: I suppose I should compute a weighted average of the midpoints of each edge of the polytope but I can't see how this is related to the above formulation.

• as any coherent MCMC, the walk in the state space has to be s.t. it satisfies the detailed balance, which, for the present case, the text tells me that it should be the target distribution $$p(x) \propto \delta^m(Sx-b)\prod_i \theta(u_i-x_i)\theta(x_i-l_i)$$ again, I have no idea how this is obtained nor how to compute them.

• You seem to be struggling with an assignment that is poorly written or explained. I think that the only person who can really help you with that is the person who wrote or gave you the assignment. – Wolfgang Bangerth Jan 18 at 16:27
• Thanks @WolfgangBangerth; do you mean the text doesn't make sense the way it's written? – Davide Papapicco Jan 19 at 15:36
• I don't have the whole assignment, nor do I know what you learned in class. For example, the notation you use may make sense to you, but we don't know what $\delta^m$ or $\theta$ stand for. The point I'm trying to make is that the only person who can help you is the instructor who gave you the assignment. – Wolfgang Bangerth Jan 21 at 14:35