In a problem it's stated the following:
Consider a simplified version of the Internet, which has only two distinct websites: Friendface, and Metube. Metube has 1 link to Friendface, and 1 link to itself. Friendface contains 2 links to Metube and 1 link to itself. We model a user’s behavior on the web as follows: at every time step k, the user follows a link on the current page; we assume that this link is chosen uniformly at random. Let x(k) ∈ {Friendface, Metube} represent the website that the user is on after k clicks.
You are given that x(0) = Friendface with probability 1 . Calculate the probability that x(k) = Metube for k → ∞.
Now in the solution basically it's stated that as time goes to infinity the probability of x at time k+1 is equal to the probability of x at time k.
My question is why? How to we know that this limit converge to this value?
OK let's try this so the probability that $x(0)=Friend Face$ is $1$. I will write this as $PF(0)=1$ and so $PM(0)=0$.
What is $PF(1)$? Well there is a $2/3$ chance the person will head on over to Metube and a $1/3$ chance they will stay so $PF(1)=1/3$ and $PM(1)=2/3$. What next? For $PF(2)$ we have $1/3.PF(1)+1/2.PM(1)$ which is $1/9+1/3=4/9$. $PM(2)=2/3.PF(1)+1/2.PM(1)=2/9+1/3=5/9$. Phew, they add to $1$ :).
$PF(3)=1/3.PF(2)+1/2.PM(2)$ and $PM(3)=2/3.PF(2)+1/2.PM(2)$.
$PF(3)=4/27+5/18=23/54$. $PM(3)=8/27+5/18=31/54$.
OK let us just assume that the sequence does converge (I know this is assuming what you want to prove but let's just take a look).
This means that $PF(n)=PF(n=1)$ and $PM(n)=PM(n=1)$.
Well generalising the above we have.
$PF(n+1)=1/3.PF(n)+1/2.PM(n)$ and $PM(n+1)=2/3.PF(n)+1/2.PM(n)$.
Substituting in $PF(n)=PF(n+1)$ and $PM(n)=PM(n+1)$ and just calling them $F$ and $M$ respectively we have.
$F=1/3.F+1/2.M$ and $M=2/3.F+1/2M$.
These both simplify to $2/3.F=1/2M$. So since $F+M=1$ we know that $F=3/7$ and $M=4/7$.
Now to answer your question. How do we know it coverges? There is a common sense answer. It doesn't look like it will oscillate and it can't shoot off to infinity. The most extreme position would me $F$ or $M$ equal to $1$ or $0$ but that will never happen as there are links back to the other site.
Our algebra has shown the existence of a (unique) equilibrium position which will act as an upper bound and the early analysis shows that we are moving there (strongly monotonically) so, by the monotone convergence theorem, the sequence will converge. https://en.wikipedia.org/wiki/Monotone_convergence_theorem