Intereting Posts

Galois Group of $x^{4}+7$
What is the *middle* digit of $3^{100000}$?
Find an integer such that when squared, the first 4 digits are '6666'.
any pattern here ? (revised 2)
$\sum_{k=-\infty}^\infty \frac{1}{(k+\alpha)^2} = \frac{\pi^2}{\sin^2\pi \alpha}$
What is the distribution of sum of a Gaussian and a Rayleigh distributed independent r.v.?
Completeness of sequence of reals with finitely many nonzero terms
How do I prove this method of determining the sign for acute or obtuse angle bisector in the angle bisector formula works?
Effect of differentiation on function growth rate
Separation axioms in uniform spaces
Understanding precisely the dot product…
How can I find the square root using pen and paper?
Integrability: Neither improper Riemann nor Lebesgue but Henstock-Kurzweil
The relationship between inner automorphisms, commutativity, normality, and conjugacy.
Can we prove directly that $M_t$ is a martingale

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.

- Nice references on Markov chains/processes?
- When the product of dice rolls yields a square
- Conditional return time of simple random walk
- Markov Chain transitional probability query.
- How can I compare two Markov processes?
- What is the difference between all types of Markov Chains?

- Calculating probability of 'at least one event occurring'
- What is the average number of draws (2 cards per draw with shuffles in between) before I had seen all 52 cards in the deck?
- Ulam spiral: Is there an “unusual amount of clumping” in prime-rich quadratic polynomials?
- Uniform distribution on the surface of unit sphere
- Identifying joint distribution
- 100 prisoners and a lightbulb
- probability density of the maximum of samples from a uniform distribution
- Maximum a Posteriori (MAP) Estimator of Exponential Random Variable with Uniform Prior
- What is the proof that covariance matrices are always semi-definite?
- Does Convergence in probability implies convergence of the mean?

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.

- Do the last digits of exponential towers really converge to a fixed sequence?
- Expand $(\vec{A}\times \nabla)\times \vec{B}$ using tensorial notation
- Covectors and Vectors
- nilpotent group is almost abelian – counterexample for infinite order case
- Prove that identity element is unique
- Asymptotic vlaue of $ f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i} $
- How to find $\sum_{k \in \mathbb{Z}}\frac1{(k+a)(k+b)}$
- Prove that $\phi(n) \geq \sqrt{n}/2$
- Do all Groups have a representation?
- find maximum area
- The endomorphism of field
- What is Octave Equivalence?
- Diagonalization and eigenvalues
- Solve $\lim_{x\to 0} \frac{\sin x-x}{x^3}$
- Generalized Hölder inequality