1
vote
1answer
18 views

Branching process: Why does the population die or explode?

Consider a population such that each member, independently from other members, at a certain instant of time is replaced by its offspring. Lets denote with $X_n$ $({n\ge 1})$ the amount of the ...
-1
votes
0answers
51 views

Represent math problems as Markov chains [on hold]

The step by step that takes to solve a math problem (algebra, calculus, etc.) could be seen as a Markov chain? When solving a problem, the next math rule that you are going to apply only depends of ...
1
vote
1answer
13 views

Limit distribution is invariant

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with a countable (but not necessarily finite) state space $S$. Suppose that there exists a limit distribution $\pi$, namely: ...
1
vote
1answer
19 views

About homogeneous Markov chains

Consider a homogeneous Markov chain $\{X_n\}_{n\in\mathbb N}$ with discrete state space $S$. Now consider the map $$T_{ij}=\text{min}\{n\in\mathbb N\,:\, X_n=j\mid X_0=i\}$$ where $T_{ij}$ is defined ...
0
votes
0answers
35 views

Question on Markov chain [closed]

I came across this problem while reading about Markov chain.... N students enter a clean room facility to do experiments. They have to leave their shoes outside the lab. After finishing the ...
0
votes
1answer
24 views

Supply the transition matrix for these (possible) Markov chains

Reading Grimmet, Stirzaker: Probability and Random Processes, which unfortunately doesn't have solutions. Trying to make sure I understand Markov chains. A die is rolled repeatedly. Which of these ...
0
votes
0answers
15 views

Probabilities in a Markov Model

I am reading a paper on Markov Models and I am trying to figure out how to compute the probabilities for the $\alpha$-pass. I am given an $N\times N$ matrix $A$, that has the probabilities of ...
1
vote
0answers
22 views

Conditional return time of simple random walk

Consider a simple random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0 = 0$. The probability to jump to the right neighbour is $p \geq \frac{1}{2}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, ...
0
votes
0answers
26 views

Exact probability distribution for hitting time of simple random walk

Consider simple random walk on the line starting from the site $y \in \mathbb{N}$. With probability $p$ the walker moves to the right and with probability $1-p$ to the left. Call $\tau$ the first time ...
0
votes
0answers
27 views

Proof of Hammersley and Clifford theorem in Besag's paper

I am reading Besag's paper on Spatial Interaction and the Statistical Analysis of Lattice Systems, see http://www.cise.ufl.edu/~anand/fa11/Besag_Spatial_interaction.pdf. In section 3, it introduces ...
0
votes
1answer
33 views

Board Game Markov Process - Transient Probabilities

I need to write an essay on the Game of Life board game, and so I studied up on Markov Chains to help me calculate the probabilities and average payoffs for the spaces; however I'm not sure whether ...
1
vote
1answer
32 views

Symmetric random walk and the distribution of the visits of some state

I need help with this problem: Let $(S_n)_n$ a symmetric random walk in $\mathbb{Z}$ i.e $S_n=X_1 + \cdots + X_n$ with $(X_n)$ iid $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$. Let $m \in ...
0
votes
1answer
72 views

How to make sense out of this: Ergodic theorem for Markov chains

We had the ergodic theorem for Markov chains, stating that: For a state space $S \subset \mathbb{N}$ and all functions $f \in L^1$ (meaning that $\sum_{s \in S} |f(s)|\pi(s) < \infty$) and an ...
3
votes
1answer
63 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
1
vote
1answer
56 views

Need help with a basic exercise about Markov chains

Suppose $\left\{ X_{n}\right\} _{n=1}^{\infty}$ is a Markov Chain taking real values. Are the following Markov Chains? $$Y_{n}=\sum_{i=1}^{n}X_{i} , Z_{n}=\left(X_{n},X_{n-1}\right)$$ Edit1 I ...
0
votes
2answers
53 views

Expected number of steps to absorbtion - Markov chain

I want to calculate the expected number of steps (transitions) needed for absorbtion. So the transition probability matrix $P$ has exactly one (lets say it is the first one) column with a $1$ and the ...
0
votes
2answers
42 views

Given a Markov-chain, what is the probability of being at a given state?

Given a Markov-chain, what is the probability of being at a given state? I drew the diagram below just as an example, there is nothing special about it but it would be nice if your answer used it as ...
0
votes
1answer
36 views

How do you find the probability of a certain state in Markov Chain?

This question appears without answer in an old exam I found (not a homework question) Suppose messages that enter a system need to be processed by two servers. They arrive at the system at a ...
9
votes
1answer
145 views

Can we qualitatively predict the strategy of the German and US teams in today's World Cup soccer match?

In today's World Cup soccer match between Germany and the US, both teams only need a draw to advance to the next round. There's been speculation about possible collusion, especially given the friendly ...
2
votes
2answers
118 views

Using Markov - Chain to find average and probability

Suppose a computer generate a random vector of n positions where each position appears on of the numbers from 1 to n. The generation is performed uniformly on the $n!$ possibilities. In the problem we ...
1
vote
1answer
32 views

Proving Product of Transition Matrices is again a Transition Matrix.

Let $P = [p_{ij}]$ be an $n\times n$ transition matrix for an $n$-state markov chain. How do you prove that $P^2$, or even better, that $P^n$ is again a transition matrix? My approach leaves me ...
5
votes
2answers
338 views

In a tournament $n$ players take part in a series of duels

I've recently been thinking about this problem and I think I solved it correctly. However, I was using a rather peculiar method with lots of algebra. I'll post my solution as an answer below. Is there ...
1
vote
0answers
54 views

Use Hasting-Metropolis to generate a random element from a large complicated combinatorial set L

Let $P$ the set of all permutations $(x_1, \ldots, x_n)$ of numbers $(1, \ldots,10)$ and $L$ the subset of $P$ where $\sum_{j=1}^{n}jx_j> a$. To use Hasting-Metropolis algorithm I followed the ...
0
votes
0answers
15 views

Skew and Kurtosis of Absorbing Markov Chains

An absorbing Markov chain $P$ can be put in canonical form: $$ P = \left( \begin{array}{cc} Q & R\\ \mathbf{0} & I_r \end{array} \right), $$ where $Q$ is a t-by-t matrix, $R$ is a nonzero ...
2
votes
1answer
22 views

Applying transition matrix to a probability vector seems to ruin its normalization

I had a little bit about stochastic processes during my "Statistical Physics" course and on my exam I got a problem with a Markov chain. My solution seems to be without computational mistakes (checked ...
2
votes
1answer
28 views

Markov chains by hand

If I have a starting point: $A_T=[0,1]$ at $T=1$ and a one step transition matrix of: $B=\left[ \begin{align} &\frac34 & \frac14& \\& \frac1{20}& \frac {19}{20} &\end{align} ...
0
votes
1answer
23 views

Why does this hold for the mean hitting time?

Let $X$ be a Markov chain and $T_A$ the hitting time. My text uses this in a proof: $$\mathbb E[T_A \ | \ X_0=k ] = \sum_{l\in S} \mathbb P(X_1=l \ | X_0=k\ )(1+\mathbb E[T_A \ | \ X_0=l ])$$ and I ...
0
votes
1answer
31 views

Integration with respect to conditional measure?

Let $(X_n)$ be a Markov chain. For $i\in S$ my text defines $$N_i:=\sum_{n=0}^\infty \mathbf 1_{\{ X_n=i \}}$$ and then, as a part of a larger proof, claims that $$\mathbb E_i(N_i)=\sum_{n=0}^\infty ...
1
vote
1answer
59 views

random walk with sticky barriers

Consider a random walk on the line 1,...,d. You start at point 1. At each step you flip a coin: heads means go left, tails means go right. If you're at 1 and get a heads, just stay where you are ...
0
votes
2answers
37 views

four state Markov chain

If there are four states:A,B,C,D. Probability of moving to the left is b and prob of moving to the right is a. If starting at state B, what is probability of arriving at state D? The hit says to ...
1
vote
0answers
33 views

Finding a probability measure

Could someone helpme with this problem? First, consider the transition kernel in $\mathbb{R^2}\times B(\mathbb{R})$ given by $K(x,A)=U_{S^1}(A-x)$. We can than define an other kernel in ...
0
votes
1answer
34 views

Markov’s inequality

The annual return, R, of a certain stock is a random variable with mean 10. Use Markov’s inequality to obtain a bound for the probability of the stock return being at least 20. Assuming now that R ...
1
vote
0answers
21 views

Visualizing second-order Markov chain

You can visualize a first-order Markov chain as a graph with nodes corresponding to states and edges corresponding to transitions. Are there any known strategies to visualize a second-order Markov ...
0
votes
1answer
38 views

Markov Chains and Return Times

Let $(X_n)_{n≥0}$ be a Markov chain with transition kernel $p$ on a countable state space $S$, starting at $x∈S$ $T^{(1)}=\inf\{n≥1:X_n=x\} \quad \quad$ first return time to $x$ ...
1
vote
0answers
26 views

Markov decision processes with action space only revealed at point of decision.

I have a problem which looks like a finite horizon Markov decision process, except the actions space at each time is revealed at the decision making point. There is no way to know before hand the ...
0
votes
1answer
50 views

Understanding detailed balance equations

I'm trying to understand how the equilibrium distribution satisfy the detailed balance equation. To my understanding, I only understand that a detailed balance equation would only be satisfied if ...
4
votes
1answer
47 views

Finding Hitting probability from Markov Chain

I have a Markov chain with states {1,2,3,4,5} which has the following transition matrix: $$P= \begin{bmatrix} 0.3 & 0 & 0.7 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0.5 & 0 ...
5
votes
1answer
87 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
2
votes
1answer
62 views

Monotonicity and Convexity of Stochastic Matrices

The definition of stochastic monotonicity and convexity is given by "Stochastic Orders and Their Applications" by Moshe Shaked and George Shanthikumar (1994) as: Let $P = \{p_{i,j} \}$ be a ...
0
votes
0answers
70 views

Application of Markov Chain to Game of Life Board Game

I need to calculate the expected outcomes for the Game of Life. I believe that if I multiply the probability of landing on a particular square with the payoff of said square and add up all these ...
2
votes
1answer
42 views

probability that a game finishes at $n$th step

A coin is flipped sequentially. The game finishes when the sequence TTH is formed(player X wins) or the sequence HTT is formed(player Y wins). I can find the expected time until absorption by X or Y ...
2
votes
1answer
53 views

Safe small wins vs. risky large wins at roulette

Short statement of problem : Two players play roulette at a casino. They both start with the same initial amount. Each player always plays his favorite bet each time, and stops playing as soon as he ...
0
votes
1answer
23 views

Calculating probability from Markov Chain

I have a Markov Chain with states {1,2,3,4,5} which has the following transition matrix below: $$P= \begin{bmatrix} 0.3 & 0 & 0.7 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0.5 ...
0
votes
1answer
83 views

Best martingale for sequence of “dozen” bets at roulette game

Jim goes the Casino to play roulette. He only makes “dozen” bets at each spin ; his probability of winning is therefore $\frac{1}{3}$ every time (to simplify, we neglect the effect of the zeros in ...
5
votes
3answers
144 views

Expected value of number of draws

We have $5$ number in a bag: $(1,3,5,7,9)$. We draw one from the bag and then put it back. We do this until the sum of the numbers can be divided by $3$. Whats the expected value of the number of ...
0
votes
1answer
43 views

Stopping time for circular random walk.

This is preparation for an exam I have coming up, not an assignment. Hope you won't mind helping. I've got a random walk, $Y_m, m = 0,1,2, \dots$ on $S = \{0,1,2,\dots,N\}$ with periodic boundaries ...
0
votes
0answers
16 views

discrete time Markov chain, difference between absorbing and recurrent classes.

In a discrete time Markov chain, are there any differences between an absorbing and a recurrent class? Recurrence is that we with probability 1 will reenter a state that we are in, this is a class ...
0
votes
0answers
12 views

Struggling to prove Markov chain property / State machine property - I can see what I need to do just can't write it

First notation, I have created the shorthand: $$P_x(A)=\mathbb{P}(A|X_0=x)$$ just to save time. I wish to prove "Lemma 1.3" which states the following: If $0<\alpha\le P_x(T_y\le k) \forall x\in ...
0
votes
1answer
49 views

Markov chain notation

In a book of stochastic approximation, in the convergence of the ODE method chapter I see the following notation : the state vector of a system $X_n$ has a dynamic representation controlled by ...
1
vote
1answer
34 views

Ehrenfest urn model expectation question

Consider the Ehrenfest urn model in which $M$ molecules are distributed between two urns, and at each time point one of the molecules is chosen at random and is then removed from its urn and placed in ...