Skip to main content
4 votes

The transition function in a Markov decision process

Elements of $A\times U\times A$ are triples $(a_1,u,a_2)$, where $a_1$ and $ a_2$ are elements of $A$ and $u$ is an element of $U$. The $\times$ gives the Cartesian product of its arguments.
Dave Clarke's user avatar
  • 20.2k
4 votes
Accepted

The transition function in a Markov decision process

The notation $T\colon A\times U\times A\to[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real. It is ...
Yuval Filmus's user avatar
4 votes

How many possible policies in a Markov Decision Process?

Looks like you are a bit confused by the notion of MDP policy. There's a detailed discussion with lots of examples in this question. A policy is any possible strategy in a given environment. Example: &...
Maxim's user avatar
  • 640
3 votes
Accepted

Probability of terminating in a state in a probabilistic algorithm

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)...
Yuval Filmus's user avatar
3 votes

Why do we need Gibbs sampling (and MCMC)?

It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time. Further, sampling from a Markov chain allows you to sample ...
David Richerby's user avatar
3 votes
Accepted

Why do we need Gibbs sampling (and MCMC)?

The approach you described sounds like the common algorithms for sampling. If by reasonable distribution, you mean a smallish finite discrete distribution, then see the following references for how to ...
eyeApps LLC's user avatar
3 votes

Can the solution to a POMDP be found using linear programming?

What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case. When the decision horizon is bounded (...
Jussi Rintanen's user avatar
3 votes

Average vs Worst-Case Hitting Time

This is an addendum to the answer by Yuval Filmus. Indeed $\phi(n)=\Theta(n)$, and the upper bound is explained in that answer. I don't understand the argument for the lower bound given there, but a ...
Yuval Peres's user avatar
3 votes
Accepted

Absorbing Markov Chains: An efficient algorithmic approach

There are several possible techniques. Let $P^t$ denote the matrix $P$ raised to the $t$th power. Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Orderability of Belief States in a POMDP?

Having recently worked on this topic, I can say that the answer to both of your questions is yes. The belief states may be partially ordered for example applying the monotone likelihood ratio, or ...
mikkola's user avatar
  • 171
2 votes
Accepted

Markov Chain Mixing Time of the Complete Graph

Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the ...
Yuval Filmus's user avatar
2 votes

Why do we need Gibbs sampling (and MCMC)?

It's because we're not sampling integers. If we were sampling integers, and the distribution were given explicitly, you are right, there would be simpler methods. But instead we often want to sample ...
D.W.'s user avatar
  • 162k
2 votes

Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations?

At temperature 0, simulated annealing degenerates into local search (also known as hill climbing). The problem with local search is that it gets stuck at local optima. Simulated annealing is a way to ...
Yuval Filmus's user avatar
2 votes

Perturbing a Markov chain to be closer to a target stationary distribution

You could use gradient descent. It is possible to compute the gradient of the objective function $\varphi(A)$ in terms of $A$, i.e., the derivative of the objective function with respect to each ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

How long a graph random walk takes to hit every vertex?

The cover time is at most the maximal hitting time multiplied by the harmonic number $1+\ldots+1/n$. This is the Mathews bound, see, e.g., Section 11.2 in [1]. In fact, the cover time can be ...
Yuval Peres's user avatar
2 votes
Accepted

Question about Markov Chains

First suppose that $p \ne 1/2$, and let $q=1-p$. If the first step is clockwise, then the problem is a gambler's ruin problem, and the chance of success (visiting all nodes) is $$\frac{1-q/p}{1-(q/p)^{...
Yuval Peres's user avatar
2 votes
Accepted

Time reversible Markov chains question

For this chain, the transition probabilities for $j \ne i$ are are $$p_{ij}=q_{ij}\,\frac{b_j}{b_i+b_j}\,.$$ Thus $\pi_i=b_i/Z$ satisfy $$\pi_i p_{ij}=\frac{b_ib_j}{Z(b_i+b_j)}=\pi_j p_{ji}\,,$$ which ...
Yuval Peres's user avatar
1 vote
Accepted

Observable Markov Model: Expected number of observations

The note probably refers to the calculation of the expected value of a random variable $T_{i}$ that describes the time "we stay" in the state $S_i$. From how I understand the question, this ...
nir shahar's user avatar
  • 11.6k
1 vote

Question about Markov Chains

Here is the idea. Let the vertices be $v_0,\ldots,v_n$, where $v_0$ is the origin and the vertices are arranged in clockwise order. The first step is either clockwise or counterclockwise — let's say ...
Yuval Filmus's user avatar
1 vote

Transition Function in MDP

I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that? There are a couple of scenarios that could lead to an agent ...
awillia91's user avatar
  • 394
1 vote

Understanding simulated annealing information theoretically

Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state. You want to find order within the disorder. Now, Metropolis and ...
BladdyK's user avatar
  • 11
1 vote
Accepted

Modeling a set of probabilistic concurrent processes

I will again refer to a lecture by Prof. Katoen. What you need here is a way of combining the DTMCs. The problem is, that a combination of DTMCs does not give you a new DTMC. This is because you want ...
J.Svejda's user avatar
  • 116
1 vote

Modeling a set of probabilistic concurrent processes

One approach is to model it as a composition of $N+1$ processes: a scheduler process, plus your $N$ basic processes. At each time step, the scheduler process selects which basic process will execute ...
D.W.'s user avatar
  • 162k
1 vote

Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification

To compute the probability for $\geq n$, you first compute the probability for an unbounded until and subtract from it the probability for $\leq n-1$. If you compare the sets of paths these formulas ...
J.Svejda's user avatar
  • 116
1 vote
Accepted

Calculating probability of reaching state in DTMC

The answer to your question very much depends on the values of the probabilities $a_{ij}$. If all are non-zero, then the DTMC forms one single strongly connected component and the probability of ...
J.Svejda's user avatar
  • 116
1 vote

Vorticity Matrix for Markov chain

One can verify that the following matrix $\Gamma$ has the desired properties: $\Gamma = [\pi]Q - Q^{\top}[\pi]$, where $[\pi]$ is a diagonal matrix with diagonal elements being the stationary ...
user121747's user avatar
1 vote

How to find optimal token set for compression?

Are there existing algorithms for it? Are there any algorithms related to the problem? Theoretical one: https://en.wikipedia.org/wiki/Sequitur_algorithm Practical one: https://encode.ru/threads/1909-...
Bulat's user avatar
  • 1,898
1 vote

Probabilisitc timed automaton

The reason that you do not find any results is thta from a scientific point of view, the well-posed questions for PTAs and MDPs are quite different: MDPs typically have a reward function assigned, ...
DCTLib's user avatar
  • 2,797
1 vote

Sampling Multiple Times From a Markov Chain

One correct way is to repeat the following 10 times: pick a random starting state, and apply the Markov chain for $T$ steps. I don't know whether your first proposal gives the correct distribution in ...
D.W.'s user avatar
  • 162k
1 vote

Maximize entrywise 1-norm of matrix product

Here's one approach, where we prune the set of candidates we examine based on the best combination seen so far. I don't know how well it will work; you'll probably have to implement and try it to ...
D.W.'s user avatar
  • 162k

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