Reputation
544
Top tag
Next privilege 1,000 Rep.
Create new tags
Badges
3 11
Newest
 Caucus
Impact
~18k people reached

  • 0 posts edited
  • 0 helpful flags
  • 21 votes cast
Nov
27
comment Equalizing Geometric means of Graph Cycles
@A.S. Yes, I agree. Thanks for the clarification!
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. Actually, the question of uniqueness is also something that I have been thinking about, but did not mention here.
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. I see your point, mostly I was looking for the edge probability assignments (I had not realized that these are related to the Perron-Frobenius eigenvector of the adjacency matrix). As stated, the proof in Shannon's paper requires ergodicity of the chain, which in turn requires that the Markov chain be both irreducible and aperiodic. This requirement can be relaxed to only irreducible.
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. Thanks for your help! The question has been answered on MO, but I would be happy to give you reputation points here. I don't know what is the best way to do that.
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. I am not sure I understand the reduction by removing edges. Please could you elaborate? My concern is that adding a new edge also affects the local constraint at nodes that the outgoing edges sum to 1.
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. In your marginalization over $(X_1,\ldots,X_{n-2})$, you still need to respect constraints imposed by the graph. For instance $X_{n-1}=1$ implies that $X_n=0$, but we have $\Pr[(10)]=\varphi^{-2}$.
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. In the example, we have $\varphi^n$ sequences asymptotically, each with probability approximately $\varphi^{-n}$.
Nov
26
comment Equalizing Geometric means of Graph Cycles
@A.S. In the example above, an arbitrary sequence of tiles of length $n$ has probability $\varphi^{-n}$. For instance any permutation of $(0)(10)(0)$ has probability $\varphi^{-4}$. I said approximately uniform because there's the boundary case that you may end with a broken tile. Eg: $(0)(0)(0)(1|$ has probability $\varphi^{-5}$. Anyway, under equality of geometric means, the probability of a sequence is only determined by its length (modulo some boundary conditions) - in particular, composition and ordering are irrelevant.
Nov
25
comment Equalizing Geometric means of Graph Cycles
@Aravind There's also the implicit constraint that everything lie in $[0,1]$. In general, there will be other solutions that are not probabilities. Anyway, there seems to be an incompatibility between the geometric mean and the outgoing edges constraint because the latter is linear, while the former is linear in log-space.
Nov
25
revised Equalizing Geometric means of Graph Cycles
added 127 characters in body
Nov
25
comment Equalizing Geometric means of Graph Cycles
@A.S. A simpler (and better) answer to your question is that equalizing the geometric means makes the probability distribution on $(X_1,\ldots,X_n)$ approximately uniform, where $X_i$ is the state of a Markov chain on the graph.
Nov
25
comment Equalizing Geometric means of Graph Cycles
@Aravind Thanks! This is an interesting concept.
Nov
25
revised Equalizing Geometric means of Graph Cycles
deleted 42 characters in body
Nov
25
comment Equalizing Geometric means of Graph Cycles
@Aravind That's just a plausibility argument. As I said, I have tried many numerical examples and I am aware of a rather indirect argument for existence due to Claude Shannon (see Theorem 8), that exploits the ergodicity of Markov chains. I would like to generalize that result.
Nov
25
comment Equalizing Geometric means of Graph Cycles
@A.S. Nice idea, but I think there is a gap. Replacing $C_iB_i$ with the pair of edges $C_iA$, $AB_i$ increases the length of the cycle, and hence changes the geometric mean.
Nov
25
comment Equalizing Geometric means of Graph Cycles
Continuing ... In fact, my question is intimately related to maximizing a quantity known as the entropy rate of a Markov chain, which has multiple interpretations (and applications). Having maximal entropy rate means that a random walker is maximally unpredictable - in the sense that under the stationary distribution, the conditional entropy $H(X_2|X_1)$ is maximized. On the other hand, if you intend to use the Markov chain as a random number generator, then maximizing entropy rate ensures that you get the highest yield of random bits per steps made by the random walk.
Nov
25
comment Equalizing Geometric means of Graph Cycles
The way I think of it is as a random tiling process. Every cycle can be viewed as a 'tile' in this tiling process. Setting all the geometric means to be the same is - in some sense - saying that it is hard to predict the next tile that will be placed, after you normalize for length of the tile. For instance, (0) and (10) are tiles for the above graph and at every time, a new tile is laid down - (0) with probability $1-p$ and (10) with probability $p$.
Nov
25
revised Equalizing Geometric means of Graph Cycles
added 97 characters in body
Nov
25
revised Equalizing Geometric means of Graph Cycles
added 97 characters in body
Nov
25
asked Equalizing Geometric means of Graph Cycles