In a village there are living N people and they decide with an interesting way about some actions. Specifically, if someone proposes an action, then all the N villagers vote for it with YES or NO. The next day each villager re-adjusts her/his opinion independently from the other villagers, and votes again with probability equal to the probability of the total (maximum) supporters of the previous day.This voting process continues until all N villagers agree on the same opinion.
- Prove that the villagers decide in finite time with probability 1.
- If the supporters of the proposal action are initially $N_0$, calculate the probability that the village adopts the proposal.
I am given that this is markov chain and if $Y_n$ is the number of supporters of the proposal on day $n$ with transition probabilities (first order):
$Y_n = i$, $Y_{n+1}$ is binomially distributed with parameter $\frac yN$. This implies $$\mathbb{P}(Y_{n+1} = j | Y_n = i) = \binom{j}{N} \left(\frac iN\right)^j \left(\frac{N-i}{N}\right)^{N-j}.$$
first of all how he ended that :$$\mathbb{P}(Y_{n+1} = j | Y_n = i) = \binom{j}{N} \left(\frac iN\right)^j \left(\frac{N-i}{N}\right)^{N-j}$$ What calculations did in order to conclude these transition probabilities?
In addition how can I answer the two sub questions ?
Best Answer
For part 1, note that at any stage the probability that the villagers all agree in the next round is bounded below by $(1/N)^N$, so the stopping time is bounded above by a geometric random variable with $p=(1/N)^N$, which is of course finite a.s.
The second part, as indicated in the comments, is best approached with martingales. We claim that $Y_n$ is martingale. By the Markov property, the distribution of $Y_{n+1}$ given $Y_n$ is the same as given $Y_n$, $\dots$, $Y_0$ so $$\mathbb E[Y_{n+1}\mid\mathcal F_n]=\mathbb E[Y_{n+1}\mid Y_n]=Y_n,$$ the last equality since $Y_{n+1}$ given $Y_n=y$ has distribution $\operatorname{Bin}(N, y/N)$. So $Y_n$ is martingale.
Let $T$ be the time that the village reaches a decision. We can verify that $\mathbb ET<\infty$ (from part 1) and the increments of $Y_n$ are bounded by $N$. So we can apply the optional stopping theorem to get that $$N_0=\mathbb EY_0=\mathbb EY_T=0\cdot\mathbb P(Y_T=0)+N\cdot\mathbb P(Y_T=N).$$