44

Let $T$ be the time spent in the mine. Conditioning on the first door the miner chooses, we get $$ \mathbb{E}[T]=\frac{1}{3}\cdot3+\frac{1}{3}(5+\mathbb{E}[T])+\frac{1}{3}(7+\mathbb{E}[T])$$ so $$ \mathbb{E}[T]=5+\frac{2}{3}\mathbb{E}[T].$$ If $\mathbb{E}[T]$ is finite, then we can conclude that $\mathbb{E}[T]=15$. To see that $\mathbb{E}[T]$ is finite, let ...


34

Collapse the six states into the two states you actually care about: "$5$" and "not-$5$". There is a well-defined transition probability from each of these to the other, so we can now work with a $2 \times 2$ matrix instead of a $6 \times 6$ matrix. This is a very common trick with Markov chains. The hard part is making sure that you don't lose any ...


32

I think that this question is best approached through careful modelling, rather than pure mathematics. Here's the approach I took. I don't claim that this is the perfect approach by any means, but it's a start. Spoiler: My simulations give a rate of approximately once every 0.66 years, for a population of 7 billion people who share US mortality statistics. ...


30

Markov chains have a finite memory, Martingales can have an infinite one. Pick a random value for $X_0$. Let the sequence of random variables $\{\epsilon_n,\,n>0\}$ be i.i.d. with mean$=E[\epsilon_{n}]=0$ and independent of $X_0$. The process governed by $X_{n+1}=X_n+\epsilon_{n+1}X_0$ is a martingale as \begin{align} &E[X_{n+1}|X_0,\dots,X_n] =E[...


27

Details of the method mentioned in @Batman's comment: We can view each square on the chessboard as a vertex on a graph consisting of $64$ vertices, and two vertices are connected by an edge if and only if a knight can move from one square to another by a single legal move. Since knight can move to any other squares starting from a random square, then the ...


26

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 $\{...


22

TL,DR: since the pagerank algorithm is an iterative application of the link matrix, the ultimate pagerank vector will look a lot like an eigenvector associated with the highest eigenvalue of the link matrix. PageRank, in linear algebraic terms. PageRank creates a vector of ranks: one element for each page; it also creates a matrix of links: each link from ...


21

Excellent suggestion by @Misha. Since $6$ is a small number, you may want to numerically explore this problem by computing the powers of the transition probability matrix. $$ P = \begin{bmatrix} 0 & 1/5 & 1/5 & 1/5 & 1/5 & 1/5 \\ 1/5 & 0 &1/5 & 1/5 & 1/5 & 1/5 \\ 1/5 & 1/5 & 0 &1/5 & 1/5 & 1/5 \\ ...


20

This is now a complete answer. It turns out that Markus was right all along : with this particular starting configuration, the number of black balls is a Markov chain, and at any point in time, the distribution of the sequence is uniform conditionned on the number of black balls in the space of sequences starting with a black ball. Let $\Omega$ be the set ...


18

The Gerontology Research Group keeps records I brought this up on the GRG and Louis Epstein posted the table "CHRONOLOGICAL OLDEST LIVING LISTED PERSONS (Since 1955)". I extracted the final column, death dates, and formatted it and extracted the intervals between the death dates of each person, reasoning that if the Oldest Person In The World who died in ...


18

Another approach to solving this is with simple recurrence. $$P(X_{n+1}=5)=\frac{P(X_n\neq5)}5$$and $$P(X_n\neq5)=1-P(X_n=5)$$ So if we let $a_n=P(X_n=5)$, then $$a_{n+1}=\frac{1-a_n}5$$ We know that $a_1=1$. We can also see easily that the stable state is $a=(1-a)/5$, or $a=1/6$. Letting $b_n=a_n-\frac16$, we have $$ b_{n+1}+\frac16=\frac{1-b_n-\frac16}...


17

Let $t$ be the expected time to get out. If he takes the second or third door he returns to the same position as the start, so the expected time after he returns is $t$. Therefore we have $$t=\frac 13(3) + \frac 13(t+5)+\frac 13(t+7)\\\frac 13t=5 \\t=15$$


16

This a problem which is probably intended to be solved using Markov chains. I will assume you have a basic knowledge of the subject. Suppose $(X_n)_{n\in\mathbb{N}}$ is a homogenous markov chain with transition matrix given by $$P=\begin{pmatrix} p & q & r\\ q & r & p\\ r & p & q \end{pmatrix}$$ where $p+q+r=1$ and $p,q,r>0$. ...


16

The probability is zero if $N$ is odd. After two steps, starting at the original vertex, the probability of returning there is $1/3$. Otherwise the walk moves to a vertex at distance $2$ from the original vertex. Starting at a vertex at distance $2$ from the original vertex, after two steps the probability it returns to the original vertex is $2/9$. ...


15

After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$. We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, ...


14

I just encounter the same problem as you do, here is my solution. I upload my solution by picture


14

You can bypass the cumbersome transition matrix method in this problem, and get a quicker explicit solution using generating functions and some algebra tricks. Your goal is to count the number of 2s, 3s, and 5s that occur in the prime factorization $ (2^A 3^B 5^C)$ of the product of N rolls of a die. The exponents of these primes increase in an additive ...


14

For $1\le i\le6,\;$ let $a_i$ be the number of dice which have the digit $i$ appearing. The product of the rolls will be a perfect square when $a_2+a_6,\;$ $a_3+a_6,\;$ and $a_5$ are all even; so we can consider two cases: $\textbf{1)}$ When $a_2, a_3, a_6$ are all odd, we get the exponential generating function $\;\;\;\displaystyle\underbrace{\big(1+x+\...


13

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 ...


13

I tried to deal with the complete problem analytically, but what I came up with seemed so involved and unenlightening that I propose a further simplification: Let's assume that after a goal is scored, the scoring team is likely enough to win by adopting a conservative approach that we can neglect the probability of the other team equalizing. Then the game ...


12

I think you are struggling because you are misunderstanding what we are intending to describe with the term steady state. You are correct, a Markov Chain is completely determined once it is defined. That means, no matter what step (or time) you are interested in, I can find the distributions for that step. This property is known as uniqueness. Though, that ...


12

For a finite MC it holds that aperiodic + irreducible $\Leftrightarrow$ ergodic $\Leftrightarrow$ regular as you expected. For an infinite MC it holds that aperiodic + irreducible + positive recurrent $\Leftrightarrow$ ergodic, and being "regular" in the infinite setting would require a more precise definition. ................................ ...


12

I believe the answer should depend on your background, aspirations, whether you want a theoretical or applied reference, In my opinion, a very good book which basic measure theory and discusses various types stochastic processes such as Markov, Levy and Brownian motion is: E. Cinlar, Probability and stochastics, Springer editions, 2011. It also has ...


12

Basic approach. I'd take advantage of some symmetries here. There are three vertices at distance $1$ from the start, three vertices at distance $2$ from the start, and one vertex at distance $3$ from the start. Show that the distance of the vertex from the start is represented by a four-state Markov chain with the following transition probabilities: $$ ...


11

For example, consider $$ \left[ \begin {array}{ccc} 0&{\frac {49}{72}}&{\frac {23}{72}} \\ 1/2&1/6&1/3\\ 1&0&0\end {array} \right] $$ which is not diagonalizable (the eigenvalue $-5/12$ has algebraic multiplicity $2$ but geometric multiplicity $1$).


11

Every Markov chain on a finite state space has an invariant distribution. As you said, this follows directly from the condition that the rows sum to $1$. It is possible for a Markov chain on a finite state space to have multiple invariant distributions. However, the Perron-Frobenius theorem tells us that these can be decomposed into distributions which are ...


11

Misha’s answer is the best approach to this problem, but finding the eigenvalues of the full $6\times6$ transition matrix is actually very easy because of its special structure. Observe that we can write the transition matrix as $M=\frac15(\mathbb1_6-I_6)$, where $\mathbb 1_6$ is the $6\times6$ matrix consisting entirely of $1$s. So, if $\mathbf v$ is an ...


11

The linear map $T(x):=(x_1,x_1+x_2,\ldots,x_1+\ldots+x_n)$ taking a vector in $[0,1]^n$ to its partial sums is volume preserving, as it corresponds to a triangular matrix of determinant 1 (or by induction.) Consider the set $A_n$ of vectors $x$ in $[0,1]^n$ such that $x_1+\ldots+x_n \le 1$. The image $T(A_n)$ is the simplex $\{y \in [0,1]^n: y_1 \le y_2 ...


10

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 ...


10

@leonbloy pointed out an interesting observation: Related conjecture (supported by simulations) : Let $T_i$ be the incremental amount of steps it takes to colour the first $i$ positions of the sequence over and above the number of steps it takes to color the first $i-1$ character. Then $$ E(T_i)=\frac{\binom{n}{2}}{\binom{i}{2}} = \frac{n(n-1)}{i(i-1)} $...


Only top voted, non community-wiki answers of a minimum length are eligible