如何模拟 Polya urn (Martingale) 之类的问题？

Question

In a village there are living N=100 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=100 agree on the same opinion.

问题：

要经过多少投票日才能让 N 个村民投票一致？

我的努力

答案必须是所需的迭代次数。

我想在 R 中模拟这个过程，它是一个类似 Polya Urn 的过程（我相信）但是这里我们没有红色 = 1 和绿色 = 1 球 urn.We 有 N 个球（选民）。

我们还有随机的 i 人在第一天 X_{0} 是，j 人在否。

因此我们有 p = i/N 和 q =j/n.

现在第二天每个村民将再次投票，但概率等于前一天的最大概率。像

votevillage <- function(n) {
  i = sample(1:N,1);i
  j = N-i;j
  p = i/N;p
  q = 1-p;q
  support = max(i,j)
  while (support != n) {
    vote = sample(c("YES","NO"),1,prob=c(1-p,p))
    support = support + vote
  }
  if (vote == "YES") 
    return(1) 
  else 
    return(0)
}   

n = 100
trials =  100000
simlist = replicate(trials, votevillage(n))
mean(simlist)

以上代码是wrong.It我的想法（有点像伪代码）。

Answer 1

如评论中所说，当然要看第一轮yes选民的分布（如果所有村民在第一轮都投yes（no）整个选举只持续1天。

以下几行显示了如何模拟投票：

nr_of_yes_votes <- function(prob, N) {
   rbinom(1, N, prob)
}

nr_of_days_until_unanimity <- function(x0, N) {
   i <- 1
   x <- x0
   while (x < N && x > 0) {
      p <- x / N
      x <- nr_of_yes_votes(p, N)
      i <- i + 1
   }
   i
}

simulate <- function(prob0, N = 100, seed = 123, reps = 10000) {
   set.seed(seed)
   x0 <- nr_of_yes_votes(prob0, N)
   mean(replicate(reps, nr_of_days_until_unanimity(x0, N)))
}

simulate(.5) ## 137.9889
simulate(0)  ## 1
simulate(1)  ## 1

直觉上，一开始的分歧越大，达成一致所需的时间就越长。此外，问题是对称的。因此，我们期望在第一次投票中存在最大分歧时天数达到峰值（这对应于 0.5 的初始投票概率）并且随着我们接近 0 而对称下降(1).

这可以用以下几行很好地显示：

ns <- vapply((p0 <- seq(0, 1, by = .01)), simulate, numeric(1))
plot(p0, ns, type = "l", xlab = expression(Prob[0]), 
     ylab = "Expected Days")

如何模拟 Polya urn (Martingale) 之类的问题？

How to simulate a Polya urn (Martingale) like problem?

r

for-loop

simulation