# Tag Info

## Hot answers tagged markov-chains

7

Most of the patterns in my collection at http://www.ics.uci.edu/~eppstein/ca/replicators/ were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators: Pick a small random seed pattern Simulate a moderate number of steps of a modified version of the cellular automaton rule, ...

7

Estimating the volume of a convex polytope and the closely related task of sampling from it have applications in private data release. Roughly, the problem you want to solve is: given a collection of numeric valued queries on a database, come up with answers to those questions that are as close as possible to the real answers, while satisfying differential ...

4

Polyhedra are widely used in program analysis as a means of representing (an overapproximation of) set of all possible states, where a state records the value of each variable in the program. If there are a set of invariants of the program variables, each of which can be represented as a linear inequality on the variables, then conjoining all of these ...

4

The set of optimal policies for one MDP may be completely different than for another MDP even if the two MPDs differ only in the rewards and/or transition probabilities. One thing you might try in order to save resources in some cases when you change the MDP (e.g. when the set of optimal policies does not change too much) is to use policy iteration to find ...

4

Hari Narayanan recentely posted a paper on the arXiv in which he uses estimating the volume of a convex polytope to prove certain results about the Littlewood-Richardson (LR) coefficients. The LR coefficients are certain integers in representation theory that have applications in geometric complexity theory, particle physics, and many other fields (see the ...

4

Why not expand the HMM to a state graph and apply a k-shortest-paths algorithm to the graph? I have a recent survey on k-best enumeration that includes the k-shortest paths problem at http://bulletin.eatcs.org/index.php/beatcs/article/view/322.

3

The "probabilistic" element in probabilistic model checking is that the system being checked is probabilistic, not that we add probabilities to an existing deterministic or non-deterministic system. Thus, what you are checking is whether a probabilistic system satisfies some property. For example "is it true that with probability at least 0.5, the system ...

3

Your question is essentially covered by Cor 9.5 in [1] which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on $G_1$. [1] Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large ...

3

see e.g.: N-Dimensional Volume Estimation of Convex Bodies: Algorithms and Applications by Sharma, Prasanna, Aswal for an example/case study in economic forecasting, ie supply chain management. Our methods can be used to quantify information content and uncertainty, in constraint regions, in a robust optimization framework. We show applications in supply ...

2

This is perhaps a nearly trivial observation, but I couldn't think of another general property just of the automorphisms that would ensure the limiting distribution is uniform. If the automorphism group of the corresponding weighted directed graph is vertex-transitive, then the limiting distribution must be uniform, since then no vertex can be ...

2

heres another angle turned up on some online investigation. the Birkoff polytope $B_n$ has many deep theoretical properties & relates to eg to perfect matchings on graphs, but volume calculations of it are very hard even for low $n$ eg as in this study by Beck and Pixton. a more direct/remarkable TCS connection arises in that a relatively recent paper ...

2

I assume that you are asking for the construction of the probability space for a given LMP. Although, I do not have a particular reference for this construction, there are a few closely related constructions that might help you. The usual way (in my oppinion) would be to construct the probability spaces via Borel $\sigma$-algebras. The following book is a ...

2

[Comment space was too short] I think it depends on what you mean by behaviour. Probabilistic automata follow in the tradition of finite automata, so their behaviour is defined in terms of their language or traces. Labelled Markov Processes follow in the tradition of process algebra, where it is known that processes can be compared using a variety of ...

2

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well Asymptotic for very large $n$, a lot of coin flips, after a long time, etc ... Equipartition Equally distributed amongst some boxes or bins, Uniformly random, Equilibrium ...

1

If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). For every "guess", fill in the gaps accordingly and train a maximum-likelihood Markov chain on the full sequence. You can even guarantee something about the ...

1

This paper shows that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}}\log t_{\mathrm{rel}})$ for all Markov chains and that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}})$ for reversible chains. The conjecture in the question is false since it's shown that $t_{\mathrm{mix}}$ can be as large as $kt_{\mathrm{rel}}.$ http://arxiv.org/abs/1310.8021

1

You may be aware of PRISM, a probabilistic model checker, and PRISM Case Studies which documents (besides others) case studies on the correctness and performance of various randomised distributed algorithms taken from the literature. It is quite common that one distributed computing problem has several variants (with different assumptions), and each variant ...

1

I am not sure whether $A_f$ is an $\omega$-regular event, but for any $\delta>0$ we can pick some $\omega$-regular $A_\delta$ such that $|\mathsf P(A_\delta) - \mathsf P_\delta(A_\delta)| \geq 1-\delta$. This follows from the fact that $\omega$-regular events form an algebra that generates a $\sigma$-algebra where $A_f$ does belong to.

1

It is not bounded sorry for the inconvenience. Here is the proof a friend gave me (thanks a lot to him): Let consider the set $W_1 = \{w = (s,w_1,\dots)| w_1 \leq n\}$. Then $\mathcal{E}^n_n$ is bigger than $\displaystyle\sum_{w\in W_1}O^n_n(w)*P(w)$. \begin{align} \sum_{w\in W_1}O^n_n(w)*P(w) &= \sum_{k=0}^n \sum_{i=0}^k {n\choose i}(1-p)^i p^{n-i}q^{...

Only top voted, non community-wiki answers of a minimum length are eligible