0
$\begingroup$

The following question is taken from the book titled "Probability models for Computer Science" written by Sheldon M. Ross.

Question:

A particle moves along n + 1 vertices that are situated on a circle in the following manner. At each stage the particle moves one step that is either in the clockwise direction with probability p or in the counter-clockwise direction with probabiity 1-p.

Starting at a specified state let T denote the time of the first return to that state. Now how to find the probability that the particle has visited all the vertices by time T

$\endgroup$
1
  • $\begingroup$ What is your question? What are your thoughts? We're not really looking for posts that are just the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Jan 7, 2022 at 21:58

2 Answers 2

2
$\begingroup$

First suppose that $p \ne 1/2$, and let $q=1-p$. If the first step is clockwise, then the problem is a gambler's ruin problem, and the chance of success (visiting all nodes) is $$\frac{1-q/p}{1-(q/p)^{n+1}} \,,$$ See [1] or [2], section 17.3 or [3]. If the first step is counterclockwise, then the chance of success is $$\frac{1-p/q}{1-(p/q)^{n+1}} \,.$$ Thus overall, the probability that the particle has visited all the vertices by time $T$ is $$p\frac{1-q/p}{1-(q/p)^{n+1}}+q \frac{1-p/q}{1-(p/q)^{n+1}} \,. \tag{*}$$

If $p=1/2$ then again there is a reduction to a gambler's ruin problem, so by [1] or [2] Section 2.1, or [3], the answer is 1/(n+1). This answer can also be obtained by taking the limit as $p \to 1/2$ in $(*)$.

[1] Feller, W. 1968. An introduction to probability theory and its applications, third edition, Vol. 1, Wiley, New York. Chapter XIV

[2] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/

[3] Grinstead, C. and L. Snell. 1997. Introduction to Probability, 2nd revised edition, American Mathematical Society, Providence. Chapter 12.

$\endgroup$
1
$\begingroup$

Here is the idea. Let the vertices be $v_0,\ldots,v_n$, where $v_0$ is the origin and the vertices are arranged in clockwise order. The first step is either clockwise or counterclockwise — let's say clockwise. Then the probability you're after is the probability that you reach $v_n$ before you reach $v_0$, starting at $v_1$. This is random walk on a line, so you should be able to analyze it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.