Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
21 views

What should be the personalisation vector for the personalised page rank algorithm?

I am trying to understand the personalised page rank algorithm. I have a graph with multiple types of nodes and I want to calculate how important other nodes are w.r.t these nodes. I am using ...
Deepak Patankar's user avatar
3 votes
0 answers
40 views

Constrained random sampling by inequalities

Assume I have $n$ random variables $x$ which need to obey a set of inequality constraints that are linear and can be written as $Ax \leq 0$. Is there a method to sample effectively from these for ...
Dan's user avatar
  • 31
0 votes
0 answers
56 views

Is a metaheuristics a Markov Decision Process?

Is a metaheuristics optimization algorithm, such as simulated annealing, a Markov Decision Process? For example, considering the combinatorial optimization problem of finding the minimum of $f : \{0,1\...
incud's user avatar
  • 459
0 votes
1 answer
29 views

Why is data generated from a randomly constructed Markov chain not compressible?

For a project I'm working on, I need to generate some data to test the Gzip compressor, and I wrote my own implementation of Markov chain for it, and it's a 2-level nested one. But when I generate ...
DannyNiu's user avatar
  • 192
0 votes
1 answer
49 views

Expected value of Markov chain after nth steps

A Markov chain $\{ X_n, n \geqslant 0\}$ with states 0, 1, 2 has the transition probability matrix $$P= \begin{bmatrix} \frac12 & \frac13 & \frac16 \\ 0 & \frac12 & \frac23 \\ \frac12 &...
Win_odd Dhamnekar's user avatar
0 votes
1 answer
39 views

Time reversible Markov chains question

Let Q be a symmetric transition probability matrix on states 1 , . . . , n; that is $q_{i,j} = q_{j,i}$ for all i , j. Consider a markov chain defined as follows. Whenever the chain is in state i, the ...
Win_odd Dhamnekar's user avatar
1 vote
1 answer
53 views

Average and max. hitting time to a specific vertex [closed]

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
fawadria's user avatar
  • 113
1 vote
0 answers
17 views

Are these representations of the Bellman Equation equivalent?

I've found two slightly different Bellman Equations. Are they totally equivalent? I see the one on the bottom has an s' in the reward. Does this or anything else about the groupings change anything ...
Ant's user avatar
  • 119
0 votes
0 answers
28 views

In Viterbi's algorithm what is the difference between the observation space and the sequence of observations?

Wikipedia has an explanation for the viterbi algorithm, in particular it describes the following summary of the inputs: What is the difference between O and Y? Also I am trying to understand what the ...
Makogan's user avatar
  • 331
1 vote
0 answers
22 views

Counting number of copies of a given tree T in a graph G. Looking for a randomised algorithm which is an FPRAS

I'm looking for a randomised algorithm (specifically an epsilon-delta approximation) which takes as input a graph G, a subgraph T (which is a tree), and outputs an approximation to the total number of ...
Gabriel Buendia's user avatar
1 vote
1 answer
26 views

Observable Markov Model: Expected number of observations

I have a question that asks me "What is the expected number of observations in a state?" with the note: $$\sum^{\infty}_{d=1}d a^{d=1} = \frac{1}{(a-1)^2}\text{ when } |a| < 1$$ Prior to ...
Ellis Thompson's user avatar
0 votes
2 answers
43 views

Question about Markov Chains

The following question is taken from the book titled "Probability models for Computer Science" written by Sheldon M. Ross. Question: A particle moves along n + 1 vertices that are situated ...
Win_odd Dhamnekar's user avatar
1 vote
1 answer
59 views

Q: Defining Markov-Chain Probability Matrix States | Specific Academic Paper

I am working on a uni project, for which i will model synthetic electricity consumption time series using Markov-Chains. I am reading through current academic literature on that topic and came across ...
Stefan 44's user avatar
1 vote
1 answer
47 views

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

I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step. On average, how ...
chausies's user avatar
  • 532
0 votes
0 answers
8 views

Inferring reward function and transition model from optimal policy

Consider an MDP where the transition model and the reward function are unknown. Consider an optimal policy $\pi^*$ generated from this MDP (say by some oracle who does know the transition model and ...
Erik M's user avatar
  • 183
1 vote
0 answers
26 views

Degree of regularity of a Markov chain

A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive. Is there a known notion of degree of regularity quantified in terms of how soon all ...
Erik M's user avatar
  • 183
0 votes
0 answers
20 views

implementing a 802.15.4 math model based on a paper. How to verify it

I am implementing a mathematic model for predicting the congestion of 802.15.4 network based on the paper: Performance analysis of IEEE 802.15.4 non-beacon mode with the unslotted CSMA/CA Based on the ...
Zihao Zou's user avatar
0 votes
1 answer
521 views

Transition Function in MDP

I got a question about who and how sets the transation function values in markov decision processes? I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right ...
Aki's user avatar
  • 1
3 votes
1 answer
266 views

Policy dependent on initial state distribution in finite horizon MDPs

Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition ...
jonem's user avatar
  • 371
-1 votes
1 answer
83 views

Asymmetric Transition Probability Matrix with uniform stationary distribution

I am solving a discrete Markov chain problem. For this I need a Markov chain whose stationary distribution is uniform(or near to uniform distribution) and transition probability matrix is asymmetric. ...
user3322017's user avatar
0 votes
0 answers
37 views

Is there any toolbox for Markov Random Field Structure Learning?

I need a toolbox or software that takes a dataset as input, detect independencies among its random variables and produces the relative Markov Random Field graphical structure from that. Can anyone ...
Masih Zaamari's user avatar
1 vote
0 answers
19 views

Concrete practical examples for discrete time markov chain with transition rewards

Can anyone show examples for discrete-time markov chains with associated transition rewards? I am searching for examples of industrial usage of markov chains where their expect and variance or ...
Necktschnagge's user avatar
2 votes
1 answer
121 views

Probability of terminating in a state in a probabilistic algorithm

Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves ...
toploz's user avatar
  • 79
0 votes
0 answers
33 views

Find consensus trajectory of how a genetic algorithm solves an optimization

I have implemented a genetic algorithm to find the evolutionary outcomes of a biological scenario. I simulate the evolution (i.e. optimization) of five traits in my model. I ran my code 100 times and ...
Armin Dadras's user avatar
0 votes
0 answers
69 views

Monopoly Matrix Coding

I am an IB student doing SL math. For my math IA i picked the topic of monopoly and the optimal way to play. However, in this IA there is a massive matrix that needs to be built to see how the long ...
Bunny's user avatar
  • 1
6 votes
1 answer
131 views

Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing through a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain whose ...
Jake's user avatar
  • 3,790
2 votes
2 answers
66 views

Modeling a set of probabilistic concurrent processes

I'm looking into discrete-time Markov chains (DTMCs) for use in analyzing a probabilistic consensus protocol. One basic thing I haven't been able to figure out is how to model a set of independent ...
ahelwer's user avatar
  • 209
4 votes
1 answer
65 views

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

I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq ...
enigma's user avatar
  • 41
2 votes
1 answer
417 views

Calculating probability of reaching state in DTMC

Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov ...
ahelwer's user avatar
  • 209
1 vote
1 answer
75 views

Vorticity Matrix for Markov chain

I have a markov chain with $Q(u,v)$ as transition probability matrix and $\pi(u)$ as stationary distribution defined on state space $\Omega$. The dimension of matrix $Q$ is $nxn$ and vector $\pi$ is $...
user3322017's user avatar
0 votes
1 answer
202 views

information theory, find entropy given Markov chain

There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below: a) The random variable representing the $i$-th output from this ...
devss's user avatar
  • 133
1 vote
1 answer
212 views

How to find optimal token set for compression?

By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like ...
shitpoet's user avatar
  • 111
1 vote
1 answer
33 views

Probabilisitc timed automaton

I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP....
Ecterion's user avatar
3 votes
1 answer
89 views

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

Suppose we are a given a Markov chain $A_0 \in \mathbb{R}^{n \times n}$ and a desired stationary probability vector $\pi_0 \in \mathbb{R}^n$. I would like to find a Markov chain that is as close as ...
Robinson Q.'s user avatar
0 votes
1 answer
58 views

Sampling Multiple Times From a Markov Chain

In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. Lets fix some $\varepsilon\in (0,1]$ as our closeness parameter....
Springberg's user avatar
2 votes
0 answers
47 views

Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
user3280193's user avatar
0 votes
0 answers
111 views

The relationship between MDP's end component and its induced MC recurrent class

Let's assume that I have an MDP $M$ which has a number of maximal end components. I also have a random policy (scheduler) $\pi$ that can convert the MDP $M$ into a Markov chain $m$. Can I argue that ...
Perissiane's user avatar
1 vote
0 answers
85 views

Game with Random Digits (Markov Chain / Coupling)

I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf I'm not asking for anything too formal (I'...
user3280193's user avatar
3 votes
1 answer
2k views

How many possible policies in a Markov Decision Process?

If a policy yields an action for a state, how come a 3-state MDP with 2 possible actions, i.e. $S = \{Hot, Mild, Cold\}$, $A = \{East, West\}$, has 8 possible policies? Isn't it 6 if there are 2 ...
daftpunk99's user avatar
1 vote
1 answer
459 views

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

I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand ...
Optimized Life's user avatar
2 votes
3 answers
563 views

Why do we need Gibbs sampling (and MCMC)?

I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$. Maybe my alternative suggestion would sound somewhat naive (even ...
Covvar's user avatar
  • 555
1 vote
0 answers
151 views

Second-order Markov text generation?

Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which ...
rb612's user avatar
  • 459
1 vote
1 answer
77 views

Maximize entrywise 1-norm of matrix product

I have $8$ sets $E_1, \ldots, E_8$, each one of size $256$, whose elements are $4\times 4$ matrices of (nonnegative) integers. I'd like to design an algorithm to find: $$\underset{M_1 \in E_1, \...
md5's user avatar
  • 646
2 votes
0 answers
97 views

Solving the following recurrence relation derived from a Markov chain

I have the following system of recursive relations on $y_{i,j}$ that are derived from a Markov chain and that I am having difficulty in solving. For $i\ge 1$ and $j \ge 1$, we have $$y_{i,j} \times (...
Landon Carter's user avatar
4 votes
1 answer
1k views

Absorbing Markov Chains: An efficient algorithmic approach

Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state. The procedure is as follows: Given the ...
David Ferris's user avatar
3 votes
0 answers
110 views

Form of conditional observation probabilities in a POMDP

Consider a partially observable Markov decision process (POMDP), see here for a complete definition. My question is in relation to the conditional observation probabilities (denoted by $O(o|s',a)$ in ...
jonem's user avatar
  • 371
1 vote
0 answers
222 views

Calculate expected values of "Craps Game" with the help of Prism Model Checker

I have modelled the craps game (https://en.wikipedia.org/wiki/Craps#Rules_of_play) as a dtmc with the prism model checker: ...
Marco Vittorini Orgeas's user avatar
0 votes
0 answers
205 views

probability matrix from digraph adjacency matrix

All I have in hand is a adjacency matrix of a digraph with equal weight on every edge, is there a very simple way to convert this to a state change probability matrix?
Henrique Almeida Marcomini's user avatar
2 votes
1 answer
382 views

Convergence of Markov model

I was learning Hidden Markov model, and encountered this theory about convergence of Markov model. For example, consider a weather model, where on a first-day probability of weather being sunny was 0....
Mihir Thatte's user avatar
3 votes
0 answers
66 views

Calssifying the Partitions of the problem Cycle Decomposition of Markov Chains

The book Cycle Representations of Markov Processes solves the problem of Mapping Stochastic Matrices induced from a Markov Chain into Partitions using a $\lambda$-preserving ($\lambda$ is a Lebesgue ...
R. S.'s user avatar
  • 147