Dgdrxrt

How do I fit a non linear curve?

Small nick on power cord from an electric alarm clock, and copper wiring exposed but intact

Film where the government was corrupt with aliens, people sent to kill aliens are given rigged visors not showing the right aliens

Strange use of "whether ... than ..." in official text

Defamation due to breach of confidentiality

Aggressive Under-Indexing and no data for missing index

Is there a way to save my career from absolute disaster?

What difference does it make using sed with/without whitespaces?

Why don't programming languages automatically manage the synchronous/asynchronous problem?

Does Germany produce more waste than the US?

Help understanding this unsettling image of Titan, Epimetheus, and Saturn's rings?

How to get the last not-null value in an ordered column of a huge table?

Is there such a thing as a proper verb, like a proper noun?

Yu-Gi-Oh cards in Python 3

Does the Idaho Potato Commission associate potato skins with healthy eating?

Can you teleport closer to a creature you are Frightened of?

Calculate the Mean mean of two numbers

Is there an equivalent of cd - for cp or mv

Reshaping json / reparing json inside shell script (remove trailing comma)

What flight has the highest ratio of timezone difference to flight time?

Does destroying a Lich's phylactery destroy the soul within it?

What happened in Rome, when the western empire "fell"?

What is the difference between "hamstring tendon" and "common hamstring tendon"?

Man transported from Alternate World into ours by a Neutrino Detector

Hitting time on linear Markov chain

0

$begingroup$

I came across this problem in a math course of mine a while back, and I haven't been able to solve it since. Anyone have any ideas?

Suppose we have a chain of $n$ vertices, such that the first vertex has an edge to the second, the $i$th vertex has an edge to the $(i-1)$th and $(i+1)$th vertices, and the $n$th vertex has an edge to only the $(n-1)$th vertex. If we perform a random walk on the graph, starting at the second vertex, what is $E(h)$, if $h$ is the number of steps it takes to reach the first vertex?

I wrote a program that performs ~100,000 random walks to find a reasonable answer, and from that, I was able to determine that it takes $O(n)$ time, but I have not been able to find any insight into the combinatorial nature of the problem that gives us this result.

How do I prove this result rigorously?

Furthermore, what is the expected hitting time $E(h_i)$ when performing a random walk starting at vertex $i$?

Note: Another result that I know from the textbook is that $E(h_n) = n^2$, but again, I have not yet been able to come up with a proof of this.

markov-chains random-walk

share|cite|improve this question

asked Mar 28 at 1:57

inavdainavda

1198

$endgroup$

add a comment | 

0

$begingroup$

I came across this problem in a math course of mine a while back, and I haven't been able to solve it since. Anyone have any ideas?

Suppose we have a chain of $n$ vertices, such that the first vertex has an edge to the second, the $i$th vertex has an edge to the $(i-1)$th and $(i+1)$th vertices, and the $n$th vertex has an edge to only the $(n-1)$th vertex. If we perform a random walk on the graph, starting at the second vertex, what is $E(h)$, if $h$ is the number of steps it takes to reach the first vertex?

I wrote a program that performs ~100,000 random walks to find a reasonable answer, and from that, I was able to determine that it takes $O(n)$ time, but I have not been able to find any insight into the combinatorial nature of the problem that gives us this result.

How do I prove this result rigorously?

Furthermore, what is the expected hitting time $E(h_i)$ when performing a random walk starting at vertex $i$?

Note: Another result that I know from the textbook is that $E(h_n) = n^2$, but again, I have not yet been able to come up with a proof of this.

markov-chains random-walk

share|cite|improve this question

asked Mar 28 at 1:57

inavdainavda

1198

$endgroup$

add a comment | 

$begingroup$

I came across this problem in a math course of mine a while back, and I haven't been able to solve it since. Anyone have any ideas?

Suppose we have a chain of $n$ vertices, such that the first vertex has an edge to the second, the $i$th vertex has an edge to the $(i-1)$th and $(i+1)$th vertices, and the $n$th vertex has an edge to only the $(n-1)$th vertex. If we perform a random walk on the graph, starting at the second vertex, what is $E(h)$, if $h$ is the number of steps it takes to reach the first vertex?

I wrote a program that performs ~100,000 random walks to find a reasonable answer, and from that, I was able to determine that it takes $O(n)$ time, but I have not been able to find any insight into the combinatorial nature of the problem that gives us this result.

How do I prove this result rigorously?

Furthermore, what is the expected hitting time $E(h_i)$ when performing a random walk starting at vertex $i$?

Note: Another result that I know from the textbook is that $E(h_n) = n^2$, but again, I have not yet been able to come up with a proof of this.

markov-chains random-walk

share|cite|improve this question

asked Mar 28 at 1:57

inavdainavda

1198

$endgroup$

share|cite|improve this question

asked Mar 28 at 1:57

inavdainavda

1198

share|cite|improve this question

asked Mar 28 at 1:57

inavdainavda

1198

asked Mar 28 at 1:57

inavdainavda

1198

asked Mar 28 at 1:57

inavdainavda

1198