# Tag Info

1

Since the singular values of $A$ are the square roots of the positive eigenvalues of $A^tA$ then a necessary and sufficient is the eingevalues of $A^tA$ smaller or equal to 1. However, I believe this is not the answer that you want. So let me give you a sufficient condition which in some sense is sharp. A sufficient condition for the singular values of a ...

1

Perron Frobenius theory says the largest eigenvalues is 1. I believe at this point, you just need the matrix to be normal, so that the spectral radius equals the operator norm.

2

I guess that this could be shown by using the inequality $\|A\|_2\leq\sqrt{\|A\|_1\|A\|_{\infty}}$ and in a more general fashion. Let $A$ be such that $\|A\|_1\leq 1$, $b$ be a vector of unit 1-norm, and let $B:=\mathrm{diag}(b)$. We have $$\|BA\|_2^2\leq\|BA\|_1\|BA\|_{\infty}.$$ Since the absolute row-sums of $A$ are bounded from above by one and the ...

21

Label the board as $\{1,2,\cdots,8\}\times\{1,2,\cdots,8\}$. A key remark is that the number of coordinates of the position of the rook which are equal to $8$ performs a Markov chain, and, obviously, the upper rightmost square is the only square on the board such that this number is $2$. Thus, one asks for the mean hitting time of $2$ by a Markov chain on ...

6

You can simplify this problem quite a bit by noting that we can classify squares on the board as being in one of three sets: Set $A$ is the set of $49$ squares that are not in the row or column of the target square; set $B$ is the set of $14$ squares that are in the row or column of the target square, but not the target square itself; and set $C$ is the set ...

0

You have the probability of a counter-clockwise (widdershins) turn :$$\mathbb P({\rm w})= \pi_1q_1+\pi_2 q_2+\pi_3q_3$$ And the probability of a clockwise turn: $$\mathbb P({\rm c})=\pi_1p_1+\pi_2 p_2+\pi_3 p_3$$ As I read it, the event of a counter-clockwise (widdershins) turn followed by five subsequent clockwise turns would likewise have a probability ...

2

By a small modification of this answer, the mean time to visit every vertex at least once, counting the vertex one starts from, is $$E(S)=\frac{N-1}{N-1}+\frac{N-1}{N-2}+\frac{N-1}{N-3}+\cdots+\frac{N-1}{2}+\frac{N-1}{1}=(N-1)H_{N-1},$$ hence, when $N\to\infty$, $$E(S)\sim N\log N.$$

0

Ok so I think I have an answer. Expected amount of time to adding 1 node=$\sum_{k=1}^{\infty }k(\frac{n}{N-1})^(k-1)(\frac{N-n}{N-1})$. Where n= number of nodes visited. Then using the properties of a geometric series we determine the expected value of steps to add a new node gets us this: $\frac{N-n}{N-1}\frac{1}{(1-\frac{n}{N-1})^2}$ Then I should be ...

0

Hint: This is almost the coupon collector's problem because the complete graph lets you visit the other vertices randomly. There is a slight change because the next coupon is never the same as the one you just got

0

Hint: what is the expected number of steps from the first time $n$ different vertices have been visited to the first time $n+1$ different vertices have been visited?

0

Here is my solution! $P=\begin{bmatrix} 1/2 &1/2 &0 &0 &0 \\ 1/2&0 &1/2 &0 &0 \\ 1/2&0 &0 &1/2 &0 \\ 1/2&0 &0 &0 &1/2 \\ 0&0 &0 &0 &1 \end{bmatrix}$ We will then treat state 4 like a recurrent state and solve for the matrix of the form $\begin{bmatrix} I ... 0 Edit 2 And again a new try... Let$\tau:=H(j)<\infty$. Otherwise the equation is fullfilled anyway, because then$h_i(k)\geq h_i(j)h_j(k))=0$. It is $$P_i(B)=P(\exists s>t>0, X_s=k,X_t=j)$$ Furthermore $$h_i(j)=P_i(\exists s>0, X_s=j)=\frac{P(\exists s>0, X_s=j,X_0=i)}{P(X_0=i)}$$ and (using the strong Markov property) $$... 2 This follows from the (strong) Markov property of the Markov chain at the first hitting time of j. Note that h_i(k)\geqslant P_i(B), where B denotes the event that the Markov chain hits j and that, after it hits j, it hits k. Conditionally on the path of the Markov chain up to the hitting time \tau of j, the probability to hit k after ... 0 Multiplying an initial vector by the k-th power of the transition matrix you will only get the distribution of your state at step k. You need to learn/return to the basics of probability theory and Markov chains. I can recommend Grimmett and Stirzaker's book Probability and Random Processes. 1 Hint: here the notation is:$$ p^{(n)} = n\text{th power of }p\\ p^{(n)}_{04} = (n\text{th power of }p)_{04} $$0 Graphviz can do that, I think. http://www.graphviz.org/ 2 Take 0<n<N and (X_n)_{n\in\mathbb{N}} a Markov chain. Then for all a_n\in E (where E is the state space) and all subsets G\subseteq E^n, F\subseteq E^{N-n} we have that$$ \mathbb{P}((X_{n+1},...,X_N)\in F|X_n=a_n,(X_{n-1},...,X_0)\in G)\\=\mathbb{P}((X_{n+1},...,X_N)\in F|X_n=a). $$Does the statement of the theorem remain ... 2 You say "because the future depends on the past," but this is not the correct characterization of a Markov Chain: for a Markov chain if you condition on the past, it only depends on the last value. So for (2), V_n conditioned on V_{n-1},\cdots,V_1, clearly depends only on V_{n-1}. Afterall, the number of 6's that occur in n throws satisfies ... 0 Adding to mnz's answer you need to solve a set of linear equations$$ P_{\infty}^T T = P_{\infty}^T $$for the entries of T. The problem will most likely be underdetermined, there can be many solutions as pointed out in above comment. At the same time you have to satisfy constraints imposed by the structure of your graph and by the requirements ... 0 Okay, ultimately I fixed a solution as below: As we want to prove that the matrix I-P_T is invertible, then it is sufficient to show that$$ (I-P_T)x = 0 \Rightarrow{x=0} $$for any x = (x_1,...,x_N)^t\in{\mathbb{R}^N}. For that, let x = (x_1,...,x_N)^t\in{\mathbb{R}^N} be such that (I-P_T)x = 0. Then,$$ \begin{eqnarray} & (I-P_T)x & = ... 1 My intuition is that since$A$describes a transition from some vector that encodes probability distribution to another vector that also encodes probability distribution,$A$is not allowed to scale up or scale down the vector along the same direction, because otherwise that vector will no longer have all its entries add up to$1$and it would no longer be a ... 1 Indeed let$X_n$denote the number of consequtive heads that have flipped at time$n$. The possible states of$X_n$are$\{0,1,2,3,4\}$since if$4$consecutive heads the process is considered to end. Given$X_n=j$the next state can be either$0$if we flip a tail or$j+1$if we flip another consecutive head, thus $$X_{n+1}|X_n=j=\begin{cases} 0, ... 0 I think you just need to use the independence Markov property: X_0, X_1,...,X_m is independent of (X_{m+n})_{n\geq 0} with respect to the probability \mathbb{P}_{[X_m=i]}. In this case follow that$$\mathbb{P}[X_{kn}=i_n|X_{(n-1)k}=i_{n-1},...,X_0=i_0]==\mathbb{P}_{[X_{(n-1)k}=i_{n-1}]}[X_{kn}=i_n|X_{(n-2)k}=i_{n-2},...,X_0=i_0]$$... 1 The temperature transition matrix is$$ A= \left( \begin{array}{cc} .7 & .4 \\ .3 & .6 \end{array} \right) $$in the sense that if the distribution of temperature at year n is given by the 2x1 column vector t^{(n)} then$$t^{(n+1)} = At^{(n)}$$First step is that you need some assumption about the first year's temperature distribution, and the ... 1 a^{(n)} is the nth power of the matrix a. hence a^{(n)}(x,y) \neq a(x,y)^n. 1 Some remarks: The summation should be over S, not only over \{1,2,\ldots,N\}. The term \delta_{ij} rightfully counts time 0 as a time spent at j when i=j. The rest of your computations is marred by misprints (X_0=i becoming X_0=1...) and forgets to account for time 0 but the idea is correct: consider the Markov chain starting from X_0=i ... 1 Your formula works correctly for d=1 (of course) and also for d=2. The way to see d=2 is that each step changes x+y by \pm 1 each with probability \frac{1}{2} and also, each step changes x-y by \pm 1 each with probability \frac{1}{2}, and those results are independent. So it is valid to multiply the two individual probabilities of ending ... 1 No. This time, there are 2d directions to choose from. From the formula for d=2, you will have to change the binomial coefficient to$$ \frac {n!}{\left(a_1!\right)^2 \left(a_2!\right)^2\dots \left(a_{d}!\right)^2 }$$for every choice of a_1\dots a_{d} so that \sum_{i=1}^{d} a_i = n/2 (a_i is the number of moves made in the direction + e_i) ... 3 Let us take n even. You have to have as many left moves than right moves. The probability of getting, for example, the first n/2 left then the next n/2 right is$$ p^{n/2}(1-p)^{n/2} $$But there are other possibilities: there are n moves, n/2 of which must be left. Hence you must multiply the base probability by \binom n{n/2} . The ... 0 I believe what you mean by 'second order,' is that your state space consists of 2 state vectors, say S1 and S2 (or hypothetically more). Therefore, your transitions are conditioned by both vectors. However, despite the fact that your transitions are conditioned by both vectors, the transitions are represented by something called the "transition matrix." ... 0 Let$$P(X_0=i_0,X_1=i_1,...,X_N=i_N)=\lambda_{i_0}p_{i_0i_1}p_{i_1i_2}...p_{i_{N-1}i_{N}}$$hold true for all N. Then it must be true that$$P(X_0=i_0,X_1=i_1,...,X_{N-1}=i_{N-1})=\lambda_{i_0}p_{i_0i_1}p_{i_1i_2}...p_{i_{N-2}i_{N-1}}$$But ... 1 In infinitely many steps i suppose. If you get to 4, you clearly get to 6, chances that this happens are: After 1 step: 1/5 After 2 step: 1/5*1/5 After 3 step: 1/5*1/5*1/5 Do you understand now which infinite sum to look at? 2 The way you described the problem is that the robots cannot stay in one place, but have to move each step. If you are at step one, you have two possible paths (to 3 and to 2), so the robot takes each path with the equal probability of 1/2. At step two there are 3 paths with each the probability of 1/3. At step 3 you have 4 possible paths, ... 0 Bayes' Theorem states that the probability of event A given event B: P(A|B) = \frac{P(A \bigcap B)}{P(B)} Thus, P(A\bigcap B) = P(A|B)*P(B) Since The first step X_1 is either 1 or -1, for all events "ever return to 0," they must be either of the following: a) X_1 = 1 \ \bigcap "ever \ return \ to \ 0" b) X_1 = -1 \ \bigcap "ever \ return \ to ... 1 Let$$E = \text{"the event that it returns to$0$"} F = \text{"the event that it goes to the right"}F^c = \text{"the event it goes to the left"}$$We let p denote the probability it has a chance of going to the right and (1 - p) of going to the left. Notice we do not assume it ever stays at 0. This is a simple random walk. By the law of ... 1 If you have enough data, then you can collect transition pairs (i to j) and do a chi-square test. If N_i is the number of transition pairs starting at i, the each transition pair (i to j) should occur N_ip_{ij} times. These are your cell expected values in the chi-square test. Note, you will need enough data so that N_ip_{ij}>5\;\; \forall ij If ... 1 Let X denote the "unbounded" system$$X\to\gamma X,$$with E\gamma\gt1 and E\log\gamma\lt0, then X_n\to0 almost surely and E(X_n)\to\infty. Let X^P denote the "bounded" system$$X^P\to\min\{\gamma X^P,P\},$$then one can couple X and X^P in such a way that, almost surely and for every n,$$X^P_n\leqslant\min\{X_n,P\}.$$Then$X_n^P\to0$... 1 Hint: The time you avoid state$j$is heuristically distributed like a geometric random variable. Imagine you had just three states, whose markov chain formed a triangle. Each time you have the possibility of jumping to state$i$, you don't and this happens with probability$1-P(X_{t=1}=i|X_t=j)$. Now generalize this. 1 This might corresponds to the contents, and probably some extensions, of the seminal work by Kai Lai Chung On the boundary theory for Markov chains, see also there for the second part. See also Chung's talk at ICM'70. 0 I came up with a very simple trick that solves the issue well enough for my situation and it's free as far as complexity goes, but does introduce a small error into the result: I defined a third absorbing state for being stuck and added a tiny transition probability to ... 1 First off, you need to choose one and only one absorbing state$a$for your equations. Let's pick state #4, so in the first set of equations,$q_4=1$, but$q_8=0$. More importantly for where you're stuck, you seem to have just thrown away two of your equations when you "cleaned up":$q_2=\frac{1}{2}(q_3+q_5)$and$q_6=\frac{1}{2}(q_1+q_7)$. If you put those ... 1 What this result says is that if$X_n = N$then$X_{n+1} = N$, which is true since$P(X_{n+1} = N | X_n = N) = 1$, as you state. Regarding your second question, the event$X_n = N$consists of all infinite sequences$X_0,X_1,X_2,\ldots$satisfying$X_n = N$. 2 We can think of the experiment as follows. At the start, we have a biased three-sided coin that outputs$6,7,8$with probabilities$5/16,3/8,5/16$; we don't care about the other outcomes, so we can just ignore them. After we see$6$, we don't care about$6$, so the probabilities of$7,8$are$6/11,5/11$. Here are the possible runs of the game:$6,8\$ or ...

2

Drawing a state diagram in terms of Markov chains will help in calculating the probabilities to some extent, and you are right in that we need to sum all the branches. The scenario of an indefinite number of rolls can be dealt with by realising that we will end up with a sum to infinity of geometric progressions whose ratio is a positive number less than ...

Top 50 recent answers are included