Tag Info

New answers tagged

1

I'm not really sure how much stricter you can get. By definition, a stochastic process is Markovian if its transition rates at any given point in time depend only on its state at the point in time. In your queuing process, the state is the size of the queue, and the transitions consist of arrivals and departures. Since, by assumption, the arrival and ...


0

Well, as you point out, the chain is constructed so that $0$ is recurrent. Then just notice that recurrence is a class property.


1

What have you done so far, where are you stuck? The transition rate matrix for the standard M/M/1 queue model is given by $$Q=\begin{pmatrix} -\lambda & \lambda \\ \mu & -(\mu+\lambda) & \lambda \\ &\mu & -(\mu+\lambda) & \lambda \\ &&\mu & -(\mu+\lambda) & \lambda &\\ &&&&\ddots \end{pmatrix}.$$ ...


0

Hmmm ... it seems that your book is confusingly using $X$ to denote both the process and the state space. Let me change the state space to $S$ to make things simpler. This is the description of a stochastic process; it is just a collection of random variables. Instead of just one or two, you have a random variable for every $t$ in some index set $T$: $$ ...


0

I don't have enough time for longer answer but as a hint let me mention the coupled Markov chains and Chernoff inequality. You could also look at Metropolis algorithm as well. I hope these three would be helpful for you.


1

Note that the question defines $N$ as the initial number of stickers and $k$ is used as a variable describing the number of remaining stickers. In your answer, you use several times $k$ for what the question calls $N$. Of course notation is arbitrary, but it is better to be consistent: use the same notation as is used in the question. i) For the first bit ...


0

The first is practically trivial, once we understand that the random variables $X$, $Y$... are not necessarily one-dimensional (scalars). So you can just define $S=(Y,W)$ (a multivariate variable) and with that notation you get the first case. Regarding the second, simplifying/abusing notation: $$P(Z | X Y ) P(Y) = \frac{P(Z X Y)}{P(XY)} P(Y)$$ and $$ P(Z ...


2

For every state $x$, $P(x_1=x\mid x_0=x)=\frac13$, hence $P(x_n=x_{n-1})=\frac13$ and $P(x_n\ne x_{n-1})=\frac23$, for every initial distribution and every $n$.


0

By the way the expression you have with $1-\lambda $ involving the spectral gap, is just the second largest eigenvalue of the transition matrix. In the case where each node has an edge to the absorbing node the rate of decay will change to $N/(N+1)$ where N is the total number of nodes in the original graph. You can see this by observing that the original ...


1

Its Guess no. 3: If you have an N x N transition matrix, then you will need to set up N linear equations, where the variables are the, as yet unknown, transition probabilities. Each equation describes the probability of being in a different state, with one equation per state. So, for State 1 (S1), in a 4 state system, you need to set up the equation: ...


1

You should be able to solve it your way. An equivalent way to solve it is by $ V = V*\left[ \begin{array}{cccc} 0 & 0 & .8 & .2 \\ .4 & .6 & 0 & 0 \\ .2 & .8 & 0 & 0\\ 0 & 0 & .7& .3\end{array} \right] $, where $V = \left[ \begin{array}{cccc}a & b & c & d \end{array} \right] $ and then solving ...


0

$P$ is already a matrix ($n \times n$). Your first equation is $(P - I) \vec{\pi} = \vec{0}$ where $I$ is the $n \times n$ identity matrix. Your second is $(1,\ldots,1) \vec{\pi} = 1$. So you get the matrix-vector equation $A \vec{\pi} = \vec{b}$ where $A$ is the $(n+1)\times n$ matrix whose first $n$ rows are $P - I$ and last row is all $1$'s, and ...


1

I think it is worth pointing out that, having daw's fine upon which to build, we can easily construct a family of irreducible transition matrices which also have a pair of complex conjugate eigenvalues, where by "irreducible" I mean there is a non-zero probability of any state transiting to any other state in one step, that is, all matrix entries lie ...


3

The matrix $$ A=\left(\begin{array}{ccc} 0&1&0\\ 0&0&1 \\ 1&0&0 \end{array}\right) $$ has row and column sum equal to one, but has complex eigenvalues. The characteristic polynomial is $$ det(\lambda I-A)= \lambda^3-1. $$


1

If you start in j, then you automatically get one count of being in the target state. Now pick your next transition k. Do a weighted average of the expected number of visits from k to j, where you weigh by the probability of going to a particular k first. Let $S_{j}$ be a random variable that counts the number of times one visits state $j$. $$ S_{j} = ...


0

The elements in the leading eigenvector can be arbitrarily close to zero and I believe this means that in arbitrary powers of the matrix, you may get that the apparent leading eigenvector of the power matrix (i.e. the entries in the matrix raised to a power applied to an arbitrary non-zero vector) have entries out of order with respect to the order of the ...


1

Let's say you're in the 211 state. Based on your assumptions the two singular opinion holders are twice as likely to switch. So two thirds of the time one of those guys switches. If they switch then you're equally likely to go to 310 or 220. So $$p_{211 \to 310} = p_{211 \to 220} = (2/3)(1/2)$$ If one of the other guys switches you have to go back to 211 so ...


1

Is it obvious to you that the waiting time generated by this procedure will still be memoryless? The exponential distribution is the only continuous distribution that is memoryless. So we can completely characterize the waiting time by just computing it's mean. $$\mu = \left(\frac{\nu_i}{\nu}\right)\frac{1}{\nu} + \left(1 - ...


2

I assume that $Y_1$ is defined to be just the value of the first throw. Let $X_i$ denote the outcome of the $i$'th throw. Then $$ P(Y_3 = 3| Y_2 = 2, Y_1 = 3) = P(X_3 = 4,5,6) = \frac{2}{6}, $$ since $X_1 = 3$ and $X_2 = 2$. So to get the second highest number to be a 3, we need to throw a number higher than a three. However $$ P(Y_3 = 3| Y_2 = 2, Y_1 = 4) = ...


0

I don't really intend this to be the accepted answer, but the problem intrigued me and I felt compelled to play with it. So maybe this will give you some ideas to move forward, in addition to the others answers. Being more programmer than mathematician these days, I decided to approach this from a different angle: to get a Monte-Carlo approximation by ...


0

Look through the diagram and calculate the chance of various changes in $(s,t)$. If you are at $(0,0)$ the chance of game ending is $\frac 12$ (a black card). The chance of gaining an $s$ is $\frac 6{52}$ The chance of gaining a $t$ is $\frac 2{52}$ If we delete the no action cases we have from $$(0,0)\to \begin {cases} end&\frac ...


1

First, with your definition, $Y_1$ is not defined. I will answer starting the chain at $Y_2$ If your "roll" is a heads or tail, calculate $P(Y_{n+1}=0|Y_{n}=0)$ and show that it depends of $n$


0

The chain must be reducible for this to happen. For an example, consider a nearest-neighbour random walk on the integer line, recurrent on the negative part, positive recurrent on the positive part, and with no transition from the latter to the former. To be specific, consider that $p(x,x+1)=p_x$ and $p(x,x-1)=1-p_x$ for every $x$, $p_x=\frac12$ for every ...


3

Your initial state is $X_0=0$. When tossing the two coins you can have the following results $\{HH, HT, TH, TT \}$ with probabilities $1/4$ each. Then in each step there are the possible transitions $$X_{n+1}=\begin{cases} X_n+1, & \text{with probability } \frac14 \{HT\} \\ X_n+0=X_n, & \text{with probability } \frac12 \{HH, TT\}\\ X_n-1, & ...


2

This is a Markov chain with transitions $x\to x+1$ with probability $\frac14$ (coin 1 = heads, coin 2 = tails), $x\to x-1$ with probability $\frac14$ (coin 1 = tails, coin 2 = heads), and $x\to x$ with probability $\frac12$ (coin 1 = coin 2), for every $x$. The steps of this random walk have mean zero hence the chain is (null) recurrent. This means that ...


3

As was noted above you have to construct the transition matrix. Say there is one umbrella in the morning at his house. How can he end up with one umbrella at his house the next morning? Lets look at the 4 cases: Rains morning and night: brings umbrella to office and then back hence remains with 1 at home Rains morning but not night: brings umbrella to ...


0

For a chain with an absorbing state, the time until absorption is asymptotically distributed according to $1 - \alpha^n$ where $\alpha$ is the Perron-Frobenius eigenvalue corresponding the the sub-stochastic matrix obtained by deleting the row and column corresponding to the absorbing state: in your case, $3$ is absorbing, so let $\tau_3$ be the time to hit ...


1

You can't find "the steps it takes" because that's a random quantity. But you can find the expected number of steps it takes, starting in a given state. In your example, let $u_1$ and $u_2$ be the expected number of steps until reaching the absorbing state, starting in states $1$ and $2$ respectively. Suppose, for example, you start in state $1$. The ...


1

Step one is to write down the four by four transition matrix: the probability of moving from one state to another. Step two is to find the limit as that matrix works on itself. For example, with one umbrella at home, there is a $p$ chance of rain, but even if it does, and he takes the umbrella to work, he will take it back. He can't take more than one ...


1

Both your answers are right. You can evaluate the integral using the gamma function: https://en.wikipedia.org/wiki/Gamma_function The gamma function will cancel the factorial, and you'll get precisely what your other method says. Or if you're lazy like me just evaluate this in Mathematica: Integrate[((l1 t)^k)/(Factorial[k]) Exp[-l1 t]*l2*Exp[-l2 t], {t, ...


1

An elegant probabilistic proof uses the notion of coupling. See Theorem 8.6 of Billingsley's Probability & Measure. For another proof see Chapter 4 of Markov Chains and Mixing Times here http://pages.uoregon.edu/dlevin/MARKOV/


0

Only for irreducible, aperiodic chains. For these chains either a stationary distribution exists or the mean recurrence time is infinite but not both. See Theorem 8.8 of Billingsley's Probability & Measure, 3e.


1

If the stationary distribution $\pi$ exists then this means that the "long-term" probability of being in state $i$ is given by $\pi(i)$. You can think of these probabilities as the proportion of time on average that the system spends in states. So the mean recurrence times are given by $1/\pi(i)$. However this does not mean that the mean recurrence times ...


2

You should find that, for every initial distribution $P^0$, the distribution $P^n$ at time $n$ is some linear combination $P^n=pR_n+(1-p)S_n$ where: $p=P^0(0)+P^0(2)+P^0(4)$ $R_n$ and $S_n$ are probability distributions $R_{2n}$ and $S_{2n+1}$ have support $\{0,2,4\}$ $S_{2n}$ and $R_{2n+1}$ have support $\{1,3\}$ $R_{2n}$ and $S_{2n+1}$ converge to ...


0

Let $p$ denote the transition matrix of the Markov chain, then $p$ is symmetric hence $p^n(x,y)=p^n(y,x)$ for every $x$ and $y$ in $S$ and, for every $x$ in $S$, $$ |S|\cdot p^{2n}(x,x)=|S|\cdot\sum_{y\in S}p^n(x,y)p^n(y,x)=\sum_{y\in S}1\cdot\sum_{y\in S}(p^n(x,y))^2. $$ By Cauchy-Schwarz inequality, the RHS is at least $$ \left(\sum_{y\in ...



Top 50 recent answers are included