## Introduction

Since my blog has been experiencing a shortage of content (mostly due to the fact that I am busy with my current research work), I decided to try out a new format that will hopefully motivate me to post more often. “Weekies” i.e. “weekly quickies” are going to be weekly posts of small puzzles that I come up with or come across on the web. I plan to follow up each “weeky” with a longer write-up of solution and discussion roughly within a month or so of the original post. In the meantime do not hesitate to post solutions and discuss the puzzle in the comments under the original post.

## Random walks

Consider the *K*_{4} graph/tetrahedron depicted below. The following questions concern different random walks starting at the vertex A.

**Q1.** Assume that at any time step we will move to a random neighboring vertex with the equal probability of 1/3. What’s the probability that we will visit all vertices of the graph before returning to A?

**Q2.** Given the same walk as in question 1, what’s the probability that we will visit any one vertex out of {B, C, D} at least *n* times before returning to A?

**Q3.** Now, let’s change our walk to have a 1/2 probability of remaining at the current vertex and probabilities of 1/6 to move to each of the neighboring vertices. How do answers to questions 1 and 2 change for this walk?

**Q4.** With the walk described in question 3, what is the expected number of steps we need to take to visit all vertices at least once?

**Q5.** Let us record the sequence of visited vertices as a string of characters A, B, C, D. Consider a random walk in question 3 and record its first 10 vertices. What’s the probability that the string “ABCD” occurs as a subsequence in the recorded sequence?

**Q6.** We can generalize the walk described in question 3 using the parameter *q* ∈ [0, 1] by letting the probability of staying at the current vertex be *q* and probability of going to any given neighbor be (1-*q*)/3. Additionally, let the start vertex be picked uniformly at random. Let *n* be the length of the sequence of vertices that we record, analogously to question 5. Let **P**_{q,n} be the distribution on the Ω={A, B, C, D}^{n} generated by the described process. Let **U**_{n} be the uniform probability distribution on the Ω. Let *D* be the total variation distance function and let us denote *d(q,n)* = *D*(**P*** _{q,n}*,

**U**

_{n}). Investigate behavior of the function

*d*: [0, 1] ⨉ ℕ → [0, 1].