It is given a finite directed graph with $v\ge2$ vertices $V_i$, such that for all indexes $i$ and $j$ (with, implicitly, $0\le i<v$ and $0\le j<v$)
- there exists at most one directed edge from $V_i$ to $V_j$, noted $E_{i,j}$;
- there exists at least a path from $V_i$ to $V_j$.
It is also given costs $c_{i,j}\in\mathbb R$ with $c>0$ when edge $E_{i,j}$ is part of the graph, and $c_{i,j}=0$ otherwise (the $v\times v$ matrix of the $c_{i,j}$ defines the graph).
A probability assignment is a $v\times v$ matrix of $p_{i,j}$ with $0<p_{i,j}\le1$ when $c_{i,j}\ne0$; with $p_{i,j}=0$ when $c_{i,j}=0$; and such that $\forall i$, $1=\sum\limits_{0\le j<v}p_{i,j}$.
For a certain probability assignment
- define any cycle's yield as$$y={\sum\limits_{i,j\text{ as in the cycle}}\log_2(1/p_{i,j})\over\sum\limits_{i,j\text{ as in the cycle}}c_{i,j}}$$
- define the guaranteed yield as the minimum of the yields of the cycles; this is well defined (see fact below).
Questions:
- Is a probability assignment maximizing the guaranteed yield uniquely defined?
- How can we efficiently find it/one?
If the problem has been studied and has a standard terminology, or just could have better tagging, I want to know!
Fact: For a certain probability assignment, the guaranteed yield is well defined, and is the yield of at least one cycle visiting no vertex more than once. Proof sketch:
- There are finitely many cycles visiting no vertex more than once, thus we can define the provisional yield as the minimum of the yields of these cycles.
- In a proof by infinite descent,
- assume a cycle with yield strictly lower than the provisional yield;
- that cycle must visit some vertex more than once; we can thus divide it into two shorter cycles, keep one with the yield no greater than the other, and end up with a new shorter cycle having a no greater yield, because for positive reals $x_0$, $x_1$, $c_0$, $c_1$, it holds that ${x_0+x_1\over c_0+c_1}\ge\min({x_0\over c_0},{x_1\over c_1})$;
- repeating the above results in contradiction, thus all cycles have yield at least the provisional yield.
Definitions used, hopefully standard and natural:
- A path from $V_i$ to $V_j$ is an ordered list of $n\ge1$ graph edge(s) $E_{u_k,v_k}$ for $0\le k<n$, such that $u_0=i$, $v_{n-1}=j$, and $k>0\implies u_k=v_{k-1}$.
- A cycle is the equivalence class of an equivalence relation on the set of paths from any vertex to itself, where two set members are equivalent if they have the same number of edges $n$ and there exists some integer $r$ such that if the first cycle has edges $E_{u_k,v_k}$, then the second cycle has edges $E_{u_{(k+r\bmod n)},v_{(k+r\bmod n)}}$; there are infinitely many cycles.
- A cycle visits no vertex more than once when, for some (or equivalently any) of its paths with $n$ edges $E_{u_k,v_k}$, it holds that $k\ne k'\implies u_k\ne u_{k'}$; there are finitely many such cycles.
Context: the problem occurs in defining probabilities for arithmetic coding, so as to obtain the best guaranteed asymptotic encoding capacity of arbitrary data into output with symbols constraints defined by the graph and costs. Ultimately, I want to encode as much arbitrary data as can be guaranteed to fit an Aztec code compatible with implementations limiting the character set. If another forum is more fit, please tell!