The smallest subtask is solvable by simulating the process sufficiently many times (and we can decrease the number of simulations needed significantly by noticing that the answer is always a fraction with a small denominator).
There is only a finite number of configurations of opinions: at any moment each of the \(n\) people will hold one of at most \(n\) starting opinions.
Instead of asking our question just for the given starting configuration, we can ask it for all states at the same time. More precisely, imagine that for each state \(S\) we have the variable \(x_S\): the expected number of days until the process finishes when starting from \(S\).
For any state \(S\) where all opinions are the same we have \(x_S = 0\).
For any other state \(S\) we can write a linear equation that relates \(x_S\) to the \(x\) values of some similar states by observing what happens on the first day. We can iterate over all possible scenarios: who is selected, to whom they talk, whether or not they convince each of them. For each scenario we can determine both the probability that it happens and the new state it leads to. Then, \(x_S\) must be 1 (for the day we just simulated) plus the weighted sum of (probability of a scenario) times (\(x\) of the state produced by that scenario).
This gives us a system of linear equations with as many equations as unknowns. We can apply Gaussian elimination to solve it, thereby determining the answers for all possible states including the given starting state.
Does the above system of equations always have a single solution? Is the answer we seek always finite? The answer to both of these questions is “yes”, but we should be a bit more dilligent and explain why.
Our process is an example of an absorbing Markov chain. For each state there’s a non-zero probability of reaching the absorbing state (i.e., the state where all opinions are the same) in a constant number of steps. This can be used to show that the probability of not being in the absorbing state decreases exponentially in time, and that in turn implies the finite expected length of the process. For a more detailed proof, look up “absorbing Markov chains” in a relevant textbook.
Of course, it does not matter who holds which opinion, only their counts in the population. For instance, if three people hold opinion X, one holds opinion Y and two hold opinion Z, the expected time until consensus is obviously the same as when one person holds opinion A, two hold opinion B and three have opinion D.
Thus, we can reduce our states from all \(n^n\) possible vectors of states to integer partitions of \(n\). Their count grows exponentially, but still slowly enough, so e.g. for \(n=20\) we still have only 627 of them. This observation allows us to solve the second subproblem.
Just as a remark, already for the second subtask it’s not really realistic to reach a sufficient precision by simulating the process. This is because you need a lot of simulations and as \(n\) increases, the individual experiments are getting quite long: the worst-case answer is quadratic in \(n\). In particular, it can be shown that for \(k=1\) and conviction rate \(p = 1\) percent if we start with \(n\) people, each with their own opinion, the expected number of days until consensus is exactly \(100(n-1)^2\).
The first step towards a polynomial-time solution is to think about the individual opinions separately.
Let’s look at the definition of the expected value we are supposed to calculate. It can be expressed in the following form: sum over all \(d\) of (\(d\) times the probability that the process ends with day \(d\)).
Of course, the process ends by one opinion gaining all \(n\) votes, and this cannot happen for two opinions at the same time. Thus, the probability that the process ends on day \(d\) is the sum of up to \(n\) probabilities of mutually exclusive events: for each starting opinion, the probability that this particular opinion is the one reaching \(n\) votes.
We can now change the order of summation: instead of
sum over all days of sum over all opinions we can get the
same result by calculating
sum over all opinions of sum over all days.
Now when we’re looking at one specific opinion, the exact numbers of other opinions in the mix don’t matter and we can pretend that we only have two opinions: ours and one another. Hence, the value of the sum for any one specific opinion is fully determined by the number of people with that opinion in the beginning. Let \(f(x)\) be that value for an opinion that starts with \(x\) occurrences.
How do we calculate \(f(x)\)? The
traditional first step method we already used in the first
solution is a good start: we can look at what happens during day 1. In
particular, for each \(y\) we can
determine the probability \(p_{x,y}\)
that we will go from having \(x\)
people with our opinion to \(y\)
people.
If \(p_{x,0}\) and/or \(p_{x,n}\) is non-zero, with that probability our opinion loses/wins already after day 1. For all other \(y\) the process is still going on. We now want to use the value \(f(y)\) to tell us the sum from that point on, but this is not trivial. The problem is that \(f(y)\) is the sum of \(d\) times (the probability of our opinion winning after exactly \(d\) days), but as we now had an extra day at the beginning, for our original sum we need to multiply each probability by \(d+1\) instead of \(d\).
What is the difference between the sum we want and the sum we defined as \(f(y)\)? Clearly, it’s exactly the sum of all probabilities – in other words, the total probability \(q(y)\) that our opinion will win if it starts with \(y\) occurrences. Once we determine \(q(y)\), we will have all we need.
Oh, but we can get the \(q(y)\) values easily. If we start from \(n\) different opinions and the process eventually terminates with probability 1, by symmetry we know that each specific opinion wins with probability \(1/n\). And now if we have a general case where one opinion starts with \(y\) people, we can have the remaining \(n-y\) people have mutually distinct opinions. And as each of those individual opinions wins \(1/n\) of experiments, our big opinion must be left with the remaining \(y/n\).
Thus, we can now calculate the values \(f(x)\).
As already suggested above, we can use the first step technique to derive a system of linear equations. Of course, solving that system in \(\Theta(n^3)\) is still too slow, but we can observe one final thing: after each day the number of occurrences of any opinion will change by at most \(k\). This means that in our system of equations all non-zero coefficients lie within \(k\) of the main diagonal, and we can solve such systems faster: it’s easily doable in \(O((n+k)k^2)\) time.
