sai
Reputation
Top tag
Next privilege 1,000 Rep.
Create new tags
 4h 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}$. 5h comment Equalizing Geometric means of Graph Cycles @A.S. In the example, we have $\varphi^n$ sequences asymptotically, each with probability approximately $\varphi^{-n}$. 5h 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. 10h 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. 10h revised Equalizing Geometric means of Graph Cycles added 127 characters in body 11h 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. 11h comment Equalizing Geometric means of Graph Cycles @Aravind Thanks! This is an interesting concept. 11h revised Equalizing Geometric means of Graph Cycles deleted 42 characters in body 12h comment Number of visits to a given state of a Markov Chain Sure, but the number of runs of $j$'s is random. For instance $$iiiiiijjiiiiijjjjjjjjiiiiiiij$$ contains 3 runs of $j$'s. The length of each of these runs is a geometric random variable. You are interested in the distribution of the sum of these geometric rvs. 13h comment Number of visits to a given state of a Markov Chain Since you are interested in a sum of geometric random variables, with a random number of terms in the sum, this seems to be relevant: en.wikipedia.org/wiki/Panjer_recursion 14h comment Number of visits to a given state of a Markov Chain When you are at $j$, the time for which you stay at $j$ is a geometric random variable with parameter $(1-p_j)$. When you are at the other state, you will stay there for a time that is geometric with parameter $p_j$. 14h 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. 1d 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. 1d 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. 1d 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$. 1d revised Equalizing Geometric means of Graph Cycles added 97 characters in body 1d revised Equalizing Geometric means of Graph Cycles added 97 characters in body 1d asked Equalizing Geometric means of Graph Cycles Nov 21 comment The Light beam Problem. Consider $N=2$. Oct 28 answered Not so obvious probability puzzle.