Here is the problem.
In graph G, on different vertices there is cat and mouse. Cat and mouse do independent
random walk, but time is synchronous, in one unit of time both cat and mouse do one step.
a)Estimate expected life duration of mouse, if cat eat mouse whenever they are on
the same vertices. They can meet on the edge without consequences. Estimate should
depend on number of edges and vertices.
b) Same as above, but G is cycle $C_{2n}$ and cat and mouse starts in maximal distance from each other. Count exactlz expected mouse life duration.
c)Same as B, but graph G is hypercube of dimension k.
My progress so far:
a) Let $G=(V,E)$, $V=\{1, \dots, n\}$
Let P be the matrix with probability distribution for random walk $P_{ij}=P(M_{t+1}=i|M_t=j)=\frac{1}{d_j}$, where $M_t$ is position of random walk after
t steps. Let $v=(\frac{1}{n}, \dots, \frac{1}{n})$ be the initial distribution vektor.
Now if we know, that Cat and Mouse distribution is virtually the same, we just need to
do estimate on the probability, that they meet together after at least t steps.
Let $C_t$ and $M_t$ be the position of cat and mouse respectively after t steps. And
let L to be life duration of Mouse.
I propose $P(C_t=M_t)=<P^tv,P^tv>$, where <> is scalar product of distribution Cat and
Mouse random walk after t steps. Because probability that they meet at vertex $i$ is
the probability $$P(C_t=M_t=i)=P(C_t=i)P(M_t=i)=(P^tv)_i^2$$
Is it correct? Assuming this, I have $P(L\leq t)\geq <P^tv,P^tv>$, I must count
the case, that cat and mouse meet earlier than at t, so there are inequalities. In
the end I need to estimate
$$E(L)=\sum_{k=1}^{\infty}kP(L=t)$$
which is by using $P(L=t)=P(L\leq t)-P(L\leq t-1)$ and telescoping the sum is
$$E(L)=\sum_{k=1}^{\infty}P(L\leq t)\geq \sum_{k=1}^{\infty}<P^tv,P^tv>$$
Problem is how to estimate this and if this is good direction if its correct.
b) Here again if cats random walk is C_t and Mouse random walk is M_t. First observation is
that on on graph $C_{2(2n+1)}$, when cat and mouse start at maximal distance from each other there is no way, they can meet, because there is odd number of edges between them.
So I assume the graph is $C_{4n}$
I can maybe do the random walk H_t=(C_t-M_t) in such way, that if graph is $C_{4n}$ then
we make from that a path on 2n+1 vertices $(1,\dots, 2n+1)$. With starting point in the middle. Distance of $H_t$ from closer of the ends of the path will correspond to distance of C_t and M_t, so if cat and mouse meet at the vertex $H_t=1$ or $H_t=2n+1$. and distribution for random walk of $H_t$ will be
$$P(H_{t+1}=H_t+1)=1/4$$ Cat moves clockwise and Mouse moves counterclockwise
$$P(H_{t+1}=H_t-1)=1/4$$ Cat moves counterclockwise and Mouse moves clockwise
$$P(H_{t+1}=H_t)=1/2$$ Both Cat and Mouse moves counterclockwise or both move clockwise
I need to count expected time, that $H_t$ meet either of the edges of the path.
To simplify I can simplify I can identify first and last vertex of the path
and have random walk of $H_t$ on graph $C_{2n}$ with these probabilities. Now
the question is what is the hitting time on cycle $C_{2n}$ with random walk as defined
for $H_t$. Starting at one vertex and moving to the vertex with maximal distance on cycle.
c) no thoughts yet, also something like b) I will update if think of something.
I hope it is understandable, any help appreciated. If I do some progress I will update.
John
Best Answer
For (c): Each corner of the hypercube can be labeled with a $k$-bit number.
The mouse starts at $000..0$, the cat at $111..1$. They start with $k$ bits different.
At each step, they both change one bit. If they start with $d$ bits different, then after that step they have either $d-2$, $d$ or $d+2$ bits different.
Work out the probabilities. It becomes a one-dimensional random walk, with those probabilities between points.