Intereting Posts

Primes dividing $11, 111, 1111, …$
A paradox on Hilbert spaces and their duals
Area of Shaded Region
Showing that the map $f(z) = \frac{1}{z} $ maps circles into circles or lines
Prove $f_n(x)=(1-x/n)^n$ converges uniformly on non-negative reals
Will $2$ linear equations with $2$ unknowns always have a solution?
Show that the angles satisfy $x+y=z$
complex integration, how to evaluate it?
Calculating the Lie algebra of $SO(2,1)$
Inequalities involving the probability density function and variance
Limit of $L_p$ norm as $ p \rightarrow 0$
A set $\,\{0,1\}^*$ is countable , but its subset $\,\{0,1\}^{\Bbb N}\,$ is uncountable?
No radical in the denominator — why?
Can we always choose the generators of an ideal of a Noetherian ring to be homogeneous?
Initial Segments of Modular Arithmetic

Consider a random walk of a king on a standard chess board, which at each step moves to a uniformly random permitted square. What’s the exact mean time to visit all squares (cover time), starting from a corner square?

Is there an algebraic solution?

- Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset $, $|S_i\cap S_i|\le 1$ for $i\ne j$
- Graph theory: minors vs topological minors
- Chromatic polynomial of a grid graph
- Counting Components via Spectra of Adjacency Matrices
- Infinite connected graph
- What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

- Enumerate non-isomorphic graphs on n vertices
- Find the probability density function of $Y=X^2$
- coupon collector and Markov chains
- What is the relationship of $\mathcal{L}_1$ (total variation) distance to hypothesis testing?
- Approximation of conditional expectation
- Conditions under which the Limit for “Measure $\to 0$” is $0$
- Software to find out adjacency matrix of a graph.
- Motivation for spectral graph theory.
- Problem with an algorithm to $3$-colour the edges of cubic graphs
- How to construct a k-regular graph?

There is *in principle* no difficulty in answering this question.

As I point out in my answer here, calculating the expected cover

time of some set $\cal S$ reduces to calculating the expected hitting time of every possible non-empty subset $A$ of $\cal S$:

$$\mathbb{E}(\text{cover time})=\sum_A (-1)^{|A|-1} \mathbb{E}(T_A)$$

These hitting times are defined by $T_A=\inf(n\geq 0: X_n\in A)$.

**Look out below!** Ignorant of chess rules, I didn’t realize that a king can move diagonally. The calculations below are based on a piece that can only move in four ways: north, south, east, or west.

Just to illustrate, let me show you the solution for a $2\times 2$ chessboard:

The expected time to cover the other 3 squares ${a,b,c}$ is equal to

$$\mathbb{E}(T_{a})+\mathbb{E}(T_{b})+\mathbb{E}(T_{c})-\mathbb{E}(T_{a,b})-\mathbb{E}(T_{a,c})-\mathbb{E}(T_{b,c})+\mathbb{E}(T_{a,b,c})$$

Standard Markov chain theory uses linear algebra to find these expected hitting times

$$\mathbb{E}(T_{a})=\mathbb{E}(T_{c})=3, \mathbb{E}(T_{b})=4,

\mathbb{E}(T_{a,b})=\mathbb{E}(T_{b,c})=2, \mathbb{E}(T_{a,c})=\mathbb{E}(T_{a,b,c})=1$$

Putting it all together, we find that the expected cover time is $3+3+4-2-2-1+1=6$.

Note that I counted the king’s initial position as already covered. If you

require a return to your starting point you can modify the above technique.

The number of terms in the sum make this method impractical for an $8\times 8$ chessboard, however!

**Added:** If my calculations are correct, the expected cover time for the $3\times 3$ board is $${140803109038245\over 4517710919176}=31.1669$$

There *is* an algebraic solution; the mean cover time from any node in a graph is known to be rational and can be found in exponential time. It’s not likely to have a simple form, though. Experimentally, I ran the following code:

```
import random
def reachable((i,j)):
ok = lambda(q):(min(q)>=1 and max(q)<=8)
return filter(ok, [(i-1,j-1), (i-1,j), (i-1,j+1), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1)])
def covertime(sq, rng=random.Random()):
seen = set([sq])
path = [sq]
while len(seen)<64:
path.append(rng.choice(reachable(path[-1])))
seen.add(path[-1])
return len(path)-1
```

I found that the mean cover time starting from a corner square was about $597$, while the mean cover time starting from a center square was larger, about $621$.

- An identity involving the Bessel function of the first kind $J_0$
- Colored Blocks Factorial
- block matrices problem
- Help with real analysis proof involving supremum
- Are my calculations of a recursive prime-generating function based on logarithms correct?
- Distance function on complete Riemannian manifold.
- Image of a union of collection of sets as union of the images
- If $A^2 = I$ (Identity Matrix) then $A = \pm I$
- Pointwise convergent and total variation
- Most efficient way to integrate $\int_0^\pi \sqrt{4\sin^2 x – 4\sin x + 1}\,dx$?
- $2^a +1$ is not divisible by $2^b-1$.
- Is $f_n$ uniformly convergent on $(0,\infty)$?
- Relation between exterior (second) derivative $d^2=0$ and second derivative in multi-variable calculus.
- Ellipse $3x^2-x+6xy-3y+5y^2=0$: what are the semi-major and semi-minor axes, displacement of centre, and angle of incline?
- Show that for any prime numbers $p,q,r$, one has $p^2+q^2 \ne r^2$.