# Tag Info

1

This is a birth-death Markov chain, so $$\nu_n = \left(\frac p{1-p}\right)^n$$ is an invariant measure for $P$, that is, $\nu P=\nu$. To normalize $\nu$, we compute $$\sum_{n=0}^\infty \nu_n = \sum_{n=0}^\infty\left(\frac p{1-p}\right)^n = \frac{1-p}{1-2p}.$$ Set $$\pi_n = \frac{\nu_n}{\sum_{k=0}^\infty \nu_k} = \left(\frac ... 1 Suppose you have a positive value for \pi(0), equal to \pi_0. Then you have the recurrence relation$$\pi(x+1)=\frac{p}{1-p} \pi(x),\pi(0)=\pi_0.$$This recurrence can be solved explicitly: you get \pi(x)=\left ( \frac{p}{1-p} \right )^x \pi_0. Now normalize that. 0 First of all, it is not true that \mathbb{E}_x \tau_x=\mathbb{E}_y \tau_x. For example consider a chain with two states: \mathcal{S}=\{x,y\} with the transition matrix \pi(i,j)=1_{\{i\neq j\}} (i.e. changing state with probability 1 at every step). In this case \mathbb{E}_x \tau_x=2>1=\mathbb{E}_y \tau_x. One way to show what you want is by ... 1 The transition matrix has the "block cycle structure"$$P=\pmatrix{0&A_0&0&0&\cdots&0\cr 0&0&A_1&0&\cdots&0\cr 0&0&0&A_2&\cdots&0\cr \vdots&&&\ddots&&\vdots\cr A_{d-1}&0&0&0&\cdots&0}$$For any dth root of ... 0 You are right, this probability is not given without any reason. Since n_i is the number of transactions involving i items, the rate at which n_i goes to n_i+1 is the rate at which orders involving i products arrive. The total rate at which orders arrive is \lambda, and the probability that any order contains i items is 1/M, so that ... 0 In general, a measure \nu:2^S\to [0,\infty)^S is said to be invariant under the stochastic kernel P which specifies the transition probabilities of X, i.e. P_{ij} = \mathbb P(X_{n+1}=j\mid X_n=i) for i,j\in S if$$\nu = \nu P. $$Now, since in this case we are also assuming$$\sum_{i\in S}P_{ij} = 1, \ j\in S $$as well as the usual assumption ... 1 HINT: The stationary distribution \pi satisfies the relationship \pi P=\pi, which is equivalent to showing \forall j\in S :$$\pi_j = \sum_{i \in S}\pi_i p_{ij}$$You can also write out \pi explicitly as a row vector where every entry is \frac{1}{5}, and P is a matrix with entries p_{ij} in row i, column j. Expanding this out and using ... 1 An exponential variable S, by definition, has a density of the form \lambda \exp(-\lambda x) where \lambda is an arbitrary positive number. This number is so characteristic of the variable that it is called the "parameter". The assignment invites you to demonstrate that \lambda S is another exponential variable, presumably by calculating its density ... 1 The probability of extinction is the smallest positive root of$$G_O(z)=z$$Where O denotes the offspring distribution, and G_O(z) its generating function at z. It is easily seen that G_O(0) is the probability of extinction in the first generation. Second, if you know about generating functions, then you know that the sum: , where X is ... 0 A Markov chain that is not time-homogeneous can have a time-varying partition in communicating classes, which can possibly destroy the irreducibility property of the state space. Think for instance of a state space where there are two big components linked only by a single state in the middle. If the transition probabilities towards (or away from) this ... 1 1. For i\lt j,\; M_j-M_i is a function of X_{i+1},\ldots,X_j only. So event S_{b+1,c}^{'} involves r.v.'s X_{b+1},\ldots,X_c only. Also, M_i is a function of X_1,\ldots,X_i only. So event S_{a,b}^{'} involves r.v.'s X_1,\ldots,X_b only. By independence of X_1,X_2,\ldots,\; the events S_{a,b} and S_{b+1,c}^{'} are independent. 2. ... 1 Assume |A|=k and |B|=n. We want to compute the average size of f(A), with f ranging over all the functions from A to B. For any j\in\{1,\ldots,k\}, there are (look at Stirling numbers of the second kind)$$ {k\brace j}\cdot j!\cdot\binom{n}{j}={k \brace j}(n)_j\tag{1} $$functions such that |f(A)|=j. Our expected value is so:$$ ...

2

A quick answer can be found using the method of indicator random variables. Let the drink types be labelled from $1$ to $n$. For each $i$ from $1$ to $n$, let random variable $X_i$ be equal to $1$ if at least one person has a drink of Type $i$, and let $X_i=0$ otherwise. Then the number $Y$ of different types drunk is given by $Y=X_1+\cdots+X_n$. Thus ...

1

Allow me a divagation. Say we have a discrete Markov chain $X=\{X_n\}$ with space of possible states $S$ and transition matrix $P=(p_{xy})_{x,y\in S}$. A vector $\pi$ with non-negative entries is said to be a stationary distribution of $X$ if $\sum_{x\in S}\pi(x)=1$ and $\pi P = \pi$, that is if it satisfies $\pi(y) = \sum_{x\in S}p_{xy}\pi(x)$ for every ...

0

A more solid explanation comes from the study of stationary distributions in Markov chains. Allow me a brief divagation. Say we have a discrete Markov chain $X=\{X_n\}$ with space of possible states $S$ and transition matrix $P=(p_{xy})_{x,y\in S}$. A vector $\pi$ with non-negative entries is said to be a stationary distribution of $X$ if $\sum_{x\in ... -1 Using the following equality, $$\mathbb{P}(X_{n + 2} = j, X_{n + 1} = l \mid X_{n} = i) = \mathbb{P}(X_{n + 2} = j \mid X_{n} = i) P(X_{n + 1} = l \mid X_{n} = i)$$ Taking sums over all the states$l$in$\mathcal{S}we have \begin{align} \sum_{l \in \mathcal{S}} \mathbb{P}(X_{n + 2} = j, X_{n + 1} = l \mid X_{n} = i) &= \sum_{l \in ... 2 I don't know of a way to use the reflection principle to prove this. It might be easier to think this way: for any walk to go from 0 to k it must, in turn, go from 0 to 1, then from 1 to 2, ..., then from k-1 to k. Conversely, any sequence of walks from 0 to 1 can be joined end-to-end to form a single path from 0 to k. So, ... 0 (i) I would transpose the matrix you have. Having all rows adding to 1 is the standard format for stochastic matrices as far as I'm aware. EDIT: As noted below by Ian, if you're coming from a linear algebra standpoint, your matrix is fine as it is. (ii) Finishing before the 4th flip assuming the first is a head just means flips 2 and 3 must be tails, ... 0 The idea is of this problem is to show the distance between the rows of the matrix P^n decreases exponentially with n. Now, the proof. First, by Chapman Kolmogorov, we know P^{n+m}=P^nP^m Second, we will denote A_{i\cdot} the i-th row of matrix A. Then, by the first observation, P^{n+m}_{i\cdot}=P^{n}_{i\cdot}P^m. This implies ... 1 This is not true. Consider, e.g., $$A=\pmatrix{1&-1\\-1&1}\quad\text{and}\quad B=\pmatrix{2&0\\0&2}.$$ BothA$and$B$satisfy the given conditions but$B$is reducible. It would be true if you replaced "$A_{ij}\leq B_{ij}\leq 0$for$i\neq j$" by "$B_{ij}\leq A_{ij}\leq 0$for$i\neq j$". This is easy: the only way how to make an ... 0 In Markov chain some one use this notation: $$E[I_A(X_n)|X_0=0]=P(X_n\in A|X_0=0).$$ But in classical probability theory this notation rappresent the conditional expectation of X given an event H (which may be the event Y=y for a random variable Y) is the average of X over all outcomes in H, that is $$E(X|H)=\frac{\sum_{w\in H}X(w)}{|H|}$$ so I think ... 1 Where did you get the statement? It looks wrong to me. A counter-example follows. Consider a chain that looks like an "$\infty$"-symbol and consists of two linked cycles of length 1000 and 1001. Let$i$be the node that links the two cycles. Whenever the chain is at the node$i$, it goes to the left cycle or the right cycle with probability$1/2$, and then ... 2 Fix$j_0, i, j_n$. By Markov property, for all$j_{n - 1}, \ldots, j_1 \in S$, where$Sdenotes the state space of this Markov chain, we have \begin{align} P[X_{n + 1} = i \mid X_n = j_n, X_{n - 1} = j_{n - 1}, \ldots, X_0 = j_0] = P[X_{n + 1} = i \mid X_n = j_n]. \end{align} Or equivalently, \begin{align} & P[X_{n + 1} = i, X_n = j_n, X_{n - 1} = j_{n ... 2 1) Firstly, we can consider the\ell_1$normalized eigenvector$\mathbf {v}= \begin{bmatrix} 1/4 & 3/8 & 3/8 \end{bmatrix}^T,$which corresponds to the dominant eigenvalue$\lambda_1 =1.$The limit$\lim\limits_{n\to\infty} M^n \cdot \mathbf x$always exists for any probability vector$\mathbf{x}$and is equal to$\mathbf v.$Indeed, one way to ... 0 Because you are computing a marginal distribution, that is, a marginal density. Say the density of$(X,Z)$is$f(x,z)$then, integrating over$z$"marginalizing out$z$" gives $$\int f(x,z)\; dz = f(x)$$ where$f(x)$is the marginal density of$X$. 1 The solution of the following system of equations will give the left eigenvector (assuming that there is a corresponding eigenvalue:$1$)$$\begin{pmatrix} P_1& P_2& P_3 \end{pmatrix}= \begin{pmatrix} P_1& P_2& P_3 \end{pmatrix} \begin{pmatrix} .4 & .2 & .4 \\ .6 & 0 & .4 \\ .2 & .5 ... 1 The conditional expectation of the number of Good states in$3$steps, given that the first state is Bad is, indeed,$1.21$as I will show below. This is to answer the parenthetic question: "[...] is there another approach without using matrices?" The states of this Markov process are$\{G,B\}$. Let the random variables$\sigma_i\$ be defined as follows ...

Top 50 recent answers are included