Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are equal? Also, I would like all outgoing edges to sum to 1.

For example, $p=\varphi^{-2}$ is a solution for the graph shown below, where $\varphi$ is the Golden ratio.

enter image description here

The geometric means for the two cycles are $(p\cdot1)^{1/2}=\varphi^{-1}$ and $(1-p)=(1-\varphi^{-2})=\varphi^{-1}$. The appearance of the Golden ratio here can be explained by observing the relation to sequences with no consecutive 1's (the number of such sequences of length $n$ is approximately $\varphi^n$).

Even though the number of constraints is much larger than the number of variables, I have not been able to construct a counterexample and I also don't know of a simple/direct proof of existence (I am aware of a purported indirect proof that exploits the ergodicity of the Markov chain - I would like to generalize this). I came across this question in my study of Markov chains. I have tried many numerical examples, and such a solution always exists (and is unique in my experience).

Any ideas, hints or references would be greatly appreciated!

Question is also on math.stackexchange (with some comments, but no answers).

  • 1
    $\begingroup$ Both Math.SE and mathoverflow have a policy about cross-posting (you can perhaps post the link from Math.SE). $\endgroup$
    – Aravind
    Nov 25, 2015 at 20:26
  • $\begingroup$ @Aravind Should I just include the link in the above question? $\endgroup$
    – sai
    Nov 25, 2015 at 20:27
  • $\begingroup$ I guess so, you could state that you did not find an answer on Math.SE. $\endgroup$
    – Aravind
    Nov 25, 2015 at 20:27

1 Answer 1


I am not 100% sure I am not misusing the Perron-Frobenius Theorem, but I think that it justifies all the assumptions I am going to make in the following. The final construction itself is very simple.

Let $V$ denote the vertex set of the underlying graph and let $A$ be the adjacency matrix, that is $A_{v,w} = 1$ if $v \to w$ and otherwise $A_{v,w} = 0$. This matrix is non-negative and irreducible, because the graph was strongly connected. Hence there is a positive eigenvalue $\lambda$ together with a right-eigenvector $c$ all of whose entries are positive. Moreover, for every $v \in V$ we have $(Ac)_v = \lambda c_v$, that is: $$ \sum_{w \colon v \to w} c_w = \lambda c_v. $$ So in particular (as all entries are positive) we have that for every directed edge $v \to w$, the value $p(v \to w) := \frac{c_w}{\lambda c_v}$ is well-defined and lies in the interval $(0, 1]$.

With this definition, we have for every vertex $v \in V$ $$ \sum_{w \colon v\to w} p(v \to w) = \frac{1}{\lambda c_v}(Ac)_v = 1. $$ Along every directed cycle, all the terms $\frac{c_v}{c_w}$ cancel out, and the accumulating power of $\lambda^{-1}$ is taken care of by definition of the geometric mean; hence every cycle has geometric mean $\lambda^{-1}$.

  • $\begingroup$ Yes, thank you! I was playing around with the spectrum of the adjacency matrix before, but could not tease this out. $\endgroup$
    – sai
    Nov 26, 2015 at 23:23
  • $\begingroup$ As a combinatorial aside, since the above assignment of edge probabilities makes the probability of every sequence $(X_1,\ldots,X_n)$ approximately $\lambda^{-n}$, the number of sequences that satisfy the graph constraints must grow as $\lambda^n$ (up to constant factors). $\endgroup$
    – sai
    Nov 26, 2015 at 23:25
  • $\begingroup$ I'm sorry, I don't quite follow - what kind of sequences do you mean and which "graph constraints"? $\endgroup$ Nov 27, 2015 at 8:53
  • $\begingroup$ Sorry, that was not clear. I am thinking of a random walker on the graph. The sequence is given by the sequence of locations of the random walker, which has constraints placed on it by the graph. $\endgroup$
    – sai
    Nov 27, 2015 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.