Intereting Posts

Integer solutions for $x^2-y^3 = 23$.
Proving formula for sum of squares with binomial coefficient
Products of CW-complexes
Substitution for bound variables in logic
How can I show this set of sequences is compact?
What would happen if ZFC were found to be inconsistent?
Ricci SCALAR curvature
how to find $\int_{0}^{1}h_n(x)dx?$
What was the book that opened your mind to the beauty of mathematics?
How exactly are the beta and gamma distributions related?
Number of straight line segments determined by $n$ points in the plane is $\frac{n^2 – n}{2}$
Soft Question: Weblinks to pages with explanation on quadratics.
What is the universal cover of SL(2,R)?
How many subspace topologies of $\mathbb{R}$?
Solutions for diophantine equation $3^a+1=2^b$

Suppose a rook starts on the lower left-most square of a standard $8 \times 8$ chess board. The board contains no other pieces.

The rook randomly makes a legal chess move with every turn (directly vertical or horizontal). The rook cannot remain stationary during a turn. What is the expected number of moves for the rook to land on the upper right-most square?

I understand the rook has 14 possible moves for every turn. The problem seems to fit the concept of Markov chains, as the probability distribution of any given move does not depend on the previous. However, I do not understand how to approach this calculation.

- Simple proof that stationary birth-death chains are reversible
- Good introductory book for Markov processes
- How can I compare two matrices?
- Chuck Norris' Coupling of Markov Chains: An Invariant Distribution
- How can I compare two Markov processes?
- Symmetric random walk and the distribution of the visits of some state

- How to calculate expected number of trials of this geometric distribution
- Calculate probability of meeting.
- Expectation of the cardinality of the intersection of subsets
- Probability and uniform distribution
- variance of number of divisors
- Probabilistic Proof of $\prod\limits_{i=1}^\infty\cos\left(\frac t{2^i}\right)=\frac{\sin t}t$
- How far do I need to drive to find an empty parking spot?
- Probability that the student can solve 5 of 7 problems on the exam
- The probability of a “double supremum” of random variable
- Interpretation of limsup-liminf of sets

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 $\{0,1,2\}$ starting from $0$ with transition probabilities as follows:

- Transition $0\to0$: probability $\frac67$
- Transition $0\to1$: probability $\frac17$
- Transition $1\to0$: probability $\frac12$
- Transition $1\to1$: probability $\frac37$
- Transition $1\to2$: probability $\frac1{14}$

Then the usual approach works: one considers the mean hitting time $t_k$ starting from state $k$, then $t_2=0$ and, conditioning on the first step of the Markov chain, one gets $$t_0=1+\tfrac67\cdot t_0+\tfrac17\cdot t_1,\qquad t_1=1+\tfrac12\cdot t_0+\tfrac37\cdot t_1+\tfrac1{14}\cdot0,$$ hence the desired expected time is $$t_0=70.$$ Perhaps surprisingly, starting from the square G7 it takes exactly as many steps to reach the (apparent) neighbour square H8 than starting from the (apparent) farthest square A1.

More generally, for a board of size $n\times n$, $$t_0=n^2+n-2.$$

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 of the target square.

If the rook is (on a square) in $A$, it has transition probabilities of $P(A\to A)=\frac{12}{14}=\frac{6}{7}$, and $P(A\to B)=\frac{2}{14}=\frac17$. If the rook is in set $B$, the transition probabilities are $P(B\to A)=\frac12$, $P(B\to B)=\frac37$, and $P(B\to C)=\frac1{14}$.

If we let $E_A$ be the expected number of moves to get from $A$ to $C$ and $E_B$ be the expected number of moves from $B$ to $C$, we can set up the following equations:

$E_B=\frac{1}{14}\cdot 1+\frac{3}{7}(E_B+1)+\frac{1}{2}(E_A+1)$ and

$E_A=\frac17(E_B+1)+\frac67(E_A+1)$.

You should be able to solve this system for $E_A$ and $E_B$ to finish off the problem.

Lets keep it simple. Wherever you are on the board, there are 14 possible moves. Therefore, every calculation will be considered in a fraction of 14. As we only need the likely amount of moves, we’ll treat every chance as absolute.

If you are on one of the two edges that can reach the destination in one move, there is a 1/14 chance of reaching it. That means that it takes 14 moves on the edge to reach the destination.

There is a 7/14, or a 1/2, chance of moving away from the edge, back to where you need two moves to reach the destination. Since you need to be on the edge 14 times before reaching the destination, 14/2 is 7. You’ll move away from the edge 7 times.

When away from the edge, it takes a 2/14, or a 1/7, chance of returning to a proper edge. That means 7 moves before reaching it. When combined with the previous short paragraph, we can multiply 7 by 7 to reach 49 moves. That is how many times it takes to reach 14 moves on the edge.

So, we get 49+14 = 63. But wait! We don’t start on the edge, we start on the opposing square. So we need another 7 moves to reach a proper edge. 63+7 = 70.

It takes 70 moves to reach the destination, starting from the opposing corner.

- Verify matrix identity $A^tD-C^tB=I$ on certain hypotheses
- Alternative proof for the integral of $1/x$ being equal to $\ln (x)$?
- Trace minimization with constraints
- Ideals in direct product of rings
- polynomial division and field extensions
- Fourier coefficient of convex function
- Applications of Pseudodifferential Operators
- AGM Inequality Proof
- Showing that the orthogonal projection in a Hilbert space is compact iff the subspace is finite dimensional
- List of Local to Global principles
- Sufficient and necessary conditions for $f,g$ such that $\Bbb F_m/(f) \cong \Bbb F_m/(g)$
- Fastest way to calculate $e^x$ up to arbitrary number of decimals?
- Application of Picard-Lindelöf to determine uniqueness of a solution to an IVP
- Partial Fractions with a Repeated and a Irreducible Quadratic factor
- Proving $\pi^3 \gt 31$