# Tag Info

1

I notice that you are an eighth grader and you have solved this gambler's ruin problem by using frog on lily pad (frankly, I don't see how you have obtained the answer) despite the reference by Math1000 not mentioning anything about expected duration of the classical gambler's ruin problem - very impressed. You may refer to page 17 of the reference below: ...

0

For (c): Each corner of the hypercube can be labeled with a $k$-bit number. The mouse starts at $000..0$, the cat at $111..1$. They start with $k$ bits different. At each step, they both change one bit. If they start with $d$ bits different, then after that step they have either $d-2$, $d$ or $d+2$ bits different. Work out the probabilities. It becomes a ...

1

It is too easy to construct such an $F$. Let, for instance, $S=\{1,2\}$ and $$P=\begin{bmatrix} p&1-p\\ q&1-q \end{bmatrix}.$$ And let $$F(.,P)=\begin{bmatrix} p&p'\\ q&1-q \end{bmatrix}$$ where $p+p'\not =1$.

0

Yes the variables $t_i$ are independent and identically distributed. The independence follows directly from the Strong Markov property. That gives that $t_i$ is independent of $t_j$ for all $j < i$. The Strong Markov property and time-homogeneity together imply that $$P[X_{s + t_i} \in A | t_i] = E[X_s \in A| X_0 = y]$$ for all $s \geq 0$. That yields ...

1

UPDATE 2: I managed to prove rigorously that the conjecture I had formulated in the first update holds: The expressions for $\pi_j$ in both formulae are off by a factor of $t$. I also figured out the most plausible reason for this mistake. Consider the partition of the state space $\{S_0,\ldots, S_{t-1}\}$ mentioned above and let $q_{ij}\equiv p_{ij}^{(t)}$ ...

0

A similar version of this question is already answered at Expected number of steps in a random walk with a boundary. I understand that here the "coin" is biased but the underlying theory is the same.

1

Yes. A Drunkards Walk follows a similar principle to Binomial Distribution; but rather than successes (and failures) in a certain number of trials, you are counting steps forward and backwards. $\mathsf P(\eta_t=m)$ is the probability that in $t$ steps of $\pm 1$ units each, you will have moved $m$ units in total; consisting of $x$ steps forward, and $y$ ...

0

Let me give an answer in a different direction: Your problem is to find the terminal strongly connected components. The complexity of this problem is not bad for any sense of bad used in computer science, but I understand that you want the most efficient algorithm. Try to look into computer science literature, in particular search on graphs. I'm not an ...

0

This is an explanation of Thomas's comment, but too long for a comment: Each strongly connected component of the transition graph that has no exit edges supports a unique stationary distribution which is ergodic. On the other hand, every stationary distribution is supported on the union of such strongly connected components (transient components have no ...

0

Not much of a formula; really just an expression that encodes the rules you've described in your question: Let $\alpha$ represent the start of the word, and $\omega$ represent the end of the word. Let $\Sigma = \{A, B, \ldots, Z, \alpha, \omega\}$ be the alphabet. Then we denote the letter-transition probabilities by $p_{\mu,\nu} \equiv P(\beta_{i+1} = ... 1 Yes. That's it. A Markov chain is a sequence of random variables$\{X_k\}_{k\in\{0..n\}}$representing$n+1$subsequent states of a system, such that for all supported values$\{i_k\}_{k\in\{0..b\}}$, and$i_c$, where$0\leq a< b< c\leq n$we have: $$\mathsf P(X_c=i_c\mid \bigcap_{k\in\{0..b\}} X_k=i_k)= \mathsf P(X_c=i_c\mid X_b=i_b)$$ So if we ... 1 I am not aware of any result on the large deviation bounds you mention, but you may want to start digging in the following article (and references therein), which offers a survey of the various model that have been introduced in literature to study the performance of CSMA-like algorithms: S.-Y. Yun, Y. Yi, J. Shin, and D.Y. Eun. Optimal CSMA: A survey. In ... 1 The idea here is to realize that eventually either all reds disappear, or all greens, whichever comes first. So the limiting distribution is extremal. Assume the subset of 1000 bacteria the predator eats every time slot is independent and uniformly distributed over all options. So, after each doubling step, each one of the 2000 bacteria has a ... 0 I found this document which support Jikai's comment. Here is a link. In this document, it tells that 'the ratio of two limiting state probabilities represents the expected number of visits to state j between two successive visits to i which is$\pi_j/\pi_i$'. So for your problem, the answer is that 1/$\pi_1$-$\pi_5/\pi_1$which is '1/(1/9) - (1/3)/(1/9) = ... 1 In fact one defines the transition kernels: $$K(\omega, j) = \Bbb{E}(1_{X_n = j} \mid \mathcal{F}_{n-1})(\omega) \quad \Bbb{P } \,a.s.$$ This means that we have a regular conditional probability that allows us to talk about the jumps of our process. The markov property consists in saying that$K(\cdot, j)$is$\sigma(X_{n-1})$measurable that is ... 1 As you point out, there is no guarantee that each of the states in a Markov Chain can be visited at any particular step$n$. Another good example with lots of impossible visits is a periodic chain where any one state can only be visited on every$d$th step, where$d$is the period. More subtle are examples on countably infinite state spaces. For example, ... 0 I think your best bet is to formulate your problem as a linear program that finds the Chebyshev center of a polyhedron. By finding the Chebyshev center of the polyhedron, you try to find the largest hyper-sphere that fits inside the convex hall of the vertices. And, the center of this hyper-sphere can be defined as the center of your polytope. Take a look ... 0 Assume we have the following image. Firstly, yes, it can represent a graph of a Markov Chain. We have the 2 communicating classes$A = \{1,2,3\}$and$B=\{4,5\}$. All states in$A$are transitive, while all states in$B$are positive recurrent. Also, it is true that all the states that belong to the same class have the same period. Clearly, the period ... 1 The chain you drew is a correct example of what you were trying to do. In the second paragraph of the question, you seem to be working with a wrong idea of periodicity. Periodicity in the context of Markov chains does not refer to periodicity of the occupation probabilities of the states as a function of time (which is, as you rightly point out, not given ... 1 You have one simple error in your matrix: the last diagonal entry should be$-4$. Everything else seems fine. Anyway, you can try to use the detailed balance equations. In particular consider the case where$k,j$differ only by$1$, since these are actually the only possible transitions. From this you get four linear equations:$\$5\pi(0)=4\pi(1) \\ ...

1

That's correct. Some comments: This notion is not attached to stochastic processes. You can use a probability vector to represent a discrete distribution in a context which involves no time dependence. In general we measure the probabilities of events, which are subsets of the sample space, rather than elements of the sample space. Traditionally we name ...

Top 50 recent answers are included