Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.