I am working on MERW (Maximal entropy random walk) for a project. I want to show that given a graph G, there is $\textbf{only one}$ aperiodic markov chain on G that maximises the entropy creation rate $\displaystyle\sum_{i,j}-\pi_i P_{ij}\log(P_{ij})$ where $P$ is the transition matrix of the markov chain (adapted to the graph) and $\pi$ its invariant measure. I don't really know how to do because I don't know if we can use optimization tools to show, as this rate (considered as a function of P) doesn't have good properties (because of the presence of $\pi$) and I haven't found any proof, other than a proof from ergodic theory that is quite difficult and more, more general (it holds for other measures than markov chains). I would like to know if any of you had an idea ? Thanks a lot
3
-
$\begingroup$ In your problem, the objective function is linear in the entries of $\pi$ while being concave in the entries of $P$. If I understand correctly, it is an instance of bilevel optimization problem as $P$ depends on $\pi$. The inner problem is quite nice as it involves a concave function and linear constraints. The unicity might follow from classical results of bilevel optimization. $\endgroup$– Gilles MordantCommented Dec 4 at 21:06
-
$\begingroup$ it is more like $\pi$ depends on $P$ as we have $\pi P = \pi$ (stationary measure) but thanks, i'll check if that idea can help ! $\endgroup$– ClaraS07Commented Dec 5 at 9:22
-
$\begingroup$ By symmetry it seems pretty obvious that the solution must be the homogeneous chain, $\pi_j=1$ with $P_{ij}=\frac 1N$. Or am I missing something? $\endgroup$– leo monsaingeonCommented Dec 9 at 11:16
Add a comment
|