The probability of the correct majority made decision

Full Text

INTRODUCTION

With the aim to increase the reliability of responsible decisions, the group decision making is used. For instance, significant calculations are tasked to several individuals, and the result is considered to be reliable if it is the same at all the individuals. Another example is obtaining experiment findings. In case of discrepancies in measuring sensors’ weak signals values, the preference is given to the majority’s data. This approach rests on the hypothesis that the decision that is made by the majority vote of some group (group of experts) is more correct than that of each expert’s individually. The major aim of this work is to verify this hypothesis and assess quantitatively the collectiveness effect.

MAIN NOTIONS AND TASK SETTING

Let one assume that the group consists of (2n+1) experts (for short - (2n+1) -group) and is characterised by vector , where  – probability that k-th expert takes the right decision. Then, by the law of total probability [1], the probability that the majority vote results in the right decision, is determined by the expression

 

$П\left(X\right)=\sum _{k=0}^n\sum _{\left\{i_1,...i_k\right\}\subset \left\{1,...,2n+1\right\}}\left(1-x_{i_1}\right)...\left(1-x_{i_k}\right)\cdot \left(x_1\cdot ...\cdot x_{2n+1}\right)/\left(x_{i_1}\cdot ...\cdot x_{i_k}\right)$. (1)

 

In the expression (1) the k-th number of the outer sum is the probability of the incorrect decision by k experts, and the sum is the probability that the incorrect decision has been made by less than half of the experts. If the fraction in (1) loses its literal sense as a result of some components equaling 0, it should be considered equal to multiplication of all components except for .

If X = (p,..., p), let the group be called homogeneous (a good one, if p > 0,5, and a bad one if p < 0,5). For this type of group, the expression (1) turns into  the Bernoulli scheme [2]: $П\left(X\right)=P_{2n+1}=\sum _{k=0}^n{C}_{2n+1}^k{p}^{2n+1-k}{q}^k$, where q =1– p. Further on, it is more convenient to deal with the probability of mistake Q_2n+1=1–P_2n+1, i.e. the probability that the group makes the incorrect decision. It is obvious,

 

$Q_{2n+1}=\sum _{k=0}^n{C}_{2n+1}^k{p}^k{q}^{2n+1-k}$. (2)

HOMOGENEOUS GROUP

Two-sided assessment of probability of mistake

Let the group be considered to be a good one. If the multiplication q(pq)ⁿ is put outside the brackets, from (2) $Q_{2n+1}=q{\left(pq\right)}^n$ $\sum _{k=0}^n{C}_{2n+1}^k\cdot {\left(q/p\right)}^{n-k}.$ is obtained. With p > 0,5 it follows that ${\left(q/p\right)}^n\le {\left(q/p\right)}^{n-k}\le 1$. This implies that $q{\left(pq\right)}^n{\left(q/p\right)}^n\sum _{k=0}^n{C}_{2n+1}^k\le Q_{2n+1}\le q{\left(pq\right)}^n\sum _{k=0}^n{C}_{2n+1}^k.$ Considering that  $\sum _{k=0}^n{C}_{2n+1}^k=0,5\sum _{k=0}^{2n+1}{C}_{2n+1}^k=2^{2n}$ [3], and making other obvious simplifications, we obtain

$q{\left(4q^2\right)}^n\le Q_{2n+1}\le q{\left(4pq\right)}^n$ (3)

 

Let us introduce the parameter α = 2p –1. It is obvious that p =0,5(1+α), q = 0,5(1–α), whereby for a good group  and for a bad one  Expressing p and q through a, the inequality (3) can be converted to

 

$q{\left({\left(1-\alpha \right)}^2\right)}^n\le Q_{2n+1}\le q{\left(1-{\alpha }^2\right)}^n$. (4)

 

For a good group 0 ≤ (1–α)² < (1–α²) < 1, means that the probability of mistake is assessed from both sides by infinitely decreasing geometric progressions. In particular, with unlimited growth in the number of experts, the probability of mistake tends towards 0.

Recurrence relations, decrease of probability of mistake

(2n+1)-group is a combination of (2n–1)-group and a pair of experts. Let be the probability that (2n–1)-group have made the correct (incorrect) decision dominating by one vote. (2n+1)-group makes the incorrect decision in the following cases:

1) (2n–1)-group have voted incorrectly by a margin of more than one vote; the probability of this equals Q_2n-1 – q₁;

2) (2n–1)-group have voted incorrectly by a margin of one vote, whereas a pair of experts has at least one that voted incorrectly; the probability of this event equals q₁(1–p²);

3) (2n–1)-group have voted correctly by a margin of one vote, and a pair of experts has two that have voted incorrectly; the probability of this event equals p₁q².

Adding these probabilities together and considering that $p_1=C_{2n-1}^n{p}^n{q}^{n-1}$, $q_1=C_{2n-1}^{n-1}{p}^{n-1}{q}^n$, $p=0,5\left(1+\alpha \right)$, $q=0,5(1-\alpha )$ and $C_{2n-1}^n=C_{2n-1}^{n-1}=0,5C_{2n}^n$, we can obtain

 

$Q_{2n+1}-Q_{2n-1}=-\left(\alpha /2\right)C_{2n}^n{\left(\left(1-{\alpha }^2\right)/4\right)}^n$. (5)

 

For a good group (0< α ≤ 1) the right side (5) is negative, wherefrom it can be seen that the sequence Q_2n+1 is a decreasing one, i.e. adding an additional pair of experts results in the decrease of probability of mistake.

Economical calculation formula

Having recorded Q_2n+1 as Q₁+ (Q₃ – Q₁) +...+ (Q_2n+1 – Q_2n-1), putting subtractions (Q_2k+1– Q_2k–1) from (5) and considering that Q₁= q = 0,5(1–α), we can obtain for Q_2n+1 the following representation:

$Q_{2n+1}=\left(1/2\right)-\left(\alpha /2\right)\sum _{k=0}^n{C}_{2k}^k{\left(\left(1-{\alpha }^2\right)/4\right)}^k=\left(1/2\right)-\left(\alpha /2\right)\sum _{k=0}^n{A}_k{x}^k$, (6)

where $x=1-{\alpha }^2$, $A_k=C_{2k}^k/4^k$.

 

Let us also consider that, in accordance with [4] $A_k=C_{2k}^k/4^k=\left(2k-1\right)!!/\left(2k\right)!!$.

As n increases by 1, there is an additional of one term added to the addition in (6), and the already existing terms remain unchanged. In (2) as n increases, all the terms are changed. Therefore, the formula (6) is more economical for numerical calculations.

Asymptotic representation of the probability of mistake at n→∞

Considering the last representation for $A_k$, $\sum _{k=0}^n{A}_k{x}^k$ is a partial sum of binominal series with the facto r–1/2 [5]. Then $\sum _{k=0}^n{A}_k{x}^k={\left(1-x\right)}^{-1/2}=1/\alpha$, wherefrom $\sum _{k=0}^n{A}_k{x}^k=\left(1/\alpha \right)-\sum _{k=n+1}^{\infty }{A}_k{x}^k$. Putting this expression to (6) and putting the first member of the addition outside the brackets, we can obtain the following representation:

 

$Q_{2n+1}=\left(\alpha /2\right)A_{n+1}{x}^{n+1}\sum _{k=0}^{\infty }\left(A_{k+n+1}/A_{n+1}\right)\cdot x^k$. (7)

Let us prove that at n →∞ the sum in (7) tends towards $\sum _{k=0}^{\infty }{x}^k$, i.e. we will assess the subtraction of these sums. According to Wallis’ product [6]

 

$1/\sqrt{\pi \left(n+1/2\right)}<A_n<1/\sqrt{\pi n}$. (8)

 

From this above, we can easily obtain: $A_{k+n}/A_n>\sqrt{n/\left(k+n+1/2\right)}$, wherefrom we have $1-A_{k+n}/A_n<1-\sqrt{n/\left(k+n+1/2\right)}$. The right side is less than the value  consequently, 0 < 1– A_k+n+1/A_n+1< (k+1/2)/2(n+1). This means that

 

$0<\sum _{k=0}^{\infty }{x}^k-\sum _{k=0}^{\infty }\left(A_{k+n+1}/A_{n+1}\right)x^k=\sum _{k=0}^{\infty }\left(1-\left(A_{k+n+1}/A_{n+1}\right)\right)x^k<\sum _{k=0}^{\infty }\left(k+1/2\right)/2\left(n+1\right)\cdot x^k=$$1/2\left(n+1\right)\left(\sum _{k=0}^{\infty },k,,x^k,+,1,/,2,\sum _{k=0}^{\infty },x^k\right)$. (9)

 

where $\sum _{k=0}^{\infty }{x}^k=1/\left(1-x\right)$ (the sum of geometric progression [7]); $\sum _{k=0}^{\infty }k{x}^k=x/{\left(1-x\right)}^2$ [8]; wherefrom, considering $x=1-{\alpha }^2$, we have: $\sum _{k=0}^{\infty }{x}^k=1/{\alpha }^2$, $\sum _{k=0}^{\infty }k{x}^k=\left(1-{\alpha }^2\right)/{\alpha }^4$. Adding this to (9) and expressing $\sum _{k=0}^{\infty }\left(A_{k+n+1}/A_{n+1}\right)x^k$ in the resultant inequality , we can obtain:

$\left(1/{\alpha }^2\right)\left(1-1/\left(2\left(n+1\right)\right)\cdot \left(1/{\alpha }^2-1/2\right)\right)<\sum _{k=0}^{\infty }\left(A_{k+n+1}/A_{n+1}\right)x^k<1/{\alpha }^2$. (10)

The sum in (10) differs from Q_2n+1 by the multiplier (α/2) A_n+1 xⁿ⁺¹ (see. (7)). Multiplying (10) by this multiplier and assessing A_n+1 from both sides by virtue of (8), we can obtain the following two-sided assessment for Q_2n+1:

 

$\left({\left(1-{\alpha }^2\right)}^{n+1}/\left(2\alpha \cdot \sqrt{\pi \left(n+1/2\right)}\right)\right)\left(1-1/\left(2\left(n+1\right)\right)\left(1/{\alpha }^2-1/2\right)\right)<Q_{2n+1}<{\left(1-{\alpha }^2\right)}^{n+1}/\left(2\alpha \sqrt{\pi n}\right)$. (11)

 

It is obvious that the second multiplier in the left part is 1+О(1/n). Therefore, the following asymptotic representation follows from (11):

 

$Q_{2n+1}={\left(1-{\alpha }^2\right)}^{n+1}/\left(2\alpha \sqrt{\pi n}\right)\cdot \left(1+О\left(1/n\right)\right)$. (12)

 

Let us compare the assessments (4) and (11). It is seen that the second one is asymptotically more precise, i.e. for each fixed α > 0 there exists n, starting from which the range of change Q_2n+1, in (11) is more narrow than the range in (4). However, the assessment (4) has the advantage that it is even along α, whereas in (11) the range expands without limits at α→ 0. Therefore, the relevance of this or that assessment for certain calculations depends on numerical values of input data.

COLLECTIVE AVERAGE

Let us return to (2n+1)-group of the general form, which is characterised by vector X= (x₁,..., x_2n+1). Let us select such a homogeneous (2n+1)-group that has the same probability of the correct decision just the first one does. The value p of this homogeneous group (the probability of the right individual decision of its member) can be interpreted as an average value for a set of probabilities x₁,..., x_2n+1. Let them be referred to as a collective average of the values x₁,..., x_2n+1. In accordance with this definition, the collective average p of values x₁,..., x_2n+1 is a root of the expression

 

$П\left(X\right)=P_{2n+1}\left(p\right)$, (13)

lying in the interval 0 ≤ p ≤ 1, where P(X) is determined by formula (1), $P_{2n+1}\left(p\right)=П\left(p,p...p\right)=\sum _{k=0}^n{C}_{2n+1}^k{p}^{2n+1-k}{\left(1-p\right)}^k$.

Existence and uniqueness of collective average

Let us study the monotony of $\Pi$(X) by each variable, e.g. x_2n+1. Let us say that 2n-group of experts with numbers 1, …, 2n have voted by a margin of k, if the right votes have been given by k more experts than incorrect ones. The margin acquires odd values from от –2n to 2n. With k ≠ 0 the decision of (2n+1)-group does not depend on the decision of (2n+1) expert, and with  it coincides with it. It means that $\Pi$(X) =R_2n+...+ R₂+R₀ x_2n+1, where R_k – the probability of margin k. The probabilities R_2n,..., R₀ do not depend on x_2n+1, and R₀ ≥0, therefore $\Pi$(X) is either strictly increasing function (at R₀ ≥ 0), or a constant one (at R₀ = 0). The latter takes place when over half of the members of 2n-group vote unanimously, and therefore their votes cannot be divided equally. In other words, among x₁,..., x_2n there are more n components equalling 0, or more n, equalling 1. In the first case $\Pi$(X) =0, in the second $\Pi$(X) =1.

Thus, since P_2n+1(p) = $\Pi$(p, p,...p), then P_2n+1(p) strictly increases at the interval (0; 1), where it is different from 0 and 1. But P_2n+1(0) = 0, P_2n+1(1) =1. Thereby, P_2n+1(x) strictly increases by [0; 1] from 0 to 1. It is uninterrupted, therefore the equation (13) has the sole solution [9].

Note: if in the set (x₁,..., x_2n+1) there are zeros or ones, for a collective average one of the properties of the Kolmogorov mean may be breached [10]: replacement of values of any subset in the set (x₁,..., x_2n+1) for the average value of this subset does not change the average value of the whole set. Therefore, for the collective average, generally speaking, the universal representation by Kolmogorov does not take place [10, 11] in the form , where φ is some strictly monotonic function.

COLLECTIVE INEQUALITY  

Further on, it will be proved that the collective average is more than or equal to the geometric mean:

 

$p\ge g={\left(x_1\cdot ...\cdot x_m\right)}^{1/m}$, где $m=2n+1$. (14)

 

Let us start with special cases g = 0 и g = 1. In both cases, the inequality (14) is obvious, therefore it may be further assumed that 0 < g < 1. This implies that all x₁,..., x_2n+1 are different from 0 and not all of them are equal to 1.

Due to strict increase of the function P_2n+1 (14) $\iff$ P_2n+1(p) ≥ P_2n+1(g). But P_2n+1(p) =P(X) (13) and P_2n+1(g) =P(G), where G=(g,...,g). Thus, (14) $\iff$ $\Pi$(X) ≥ $\Pi$(G). And this inequality, considering exclusion of special cases, is equipotent to the statement  , which is exactly what needs proving.

 Let $g\in \left(0;1\right)$, and A is a set of vectors, the ones, that, and x₁∙...∙x_m= g^m. In this set, the function $\Pi$(X) reaches the lowest value at X=G, where G=(g,..., g).

Note: due to equality of x₁∙...∙x_m= g^m it is sufficient to prove that all components of the vector, delivering the minimum of П(X), are equal between each other.

Let us proceed to the proof. Expressing x_m from the condition x₁∙...∙x_m= g^m and putting it to $\Pi$(X), we acquire rational and fractional function of the variables x₁,..., x_m–1, an uninterrupted one since its denominator x₁∙...∙x_m–1 differs from 0 due to 0 < g < 1. And for all . Thus, the function is determined at the compactum [12], meaning it reaches the minimal value [13]. Consequently, the vector constituting the minimum $\Pi$(X), exists. Now, let us prove that it cannot have irregular components.

Let us consider the vector X$\in$A, that has more than n components equalling 1. For this $\Pi$(X)=1, whereas $\Pi$(G) < 1 (because g < 1). It means that the vector, which constitutes the minimum of the function $\Pi$(X), has no more than n components equalling 1. Let X be such a vector, and let not all of its components be equal to each other. Without limiting the generality, it can be assumed that x₁≠ x₂. Let us prove that then the value of $\Pi$(X) is not the lowest at A.

Since all the components are different from 0, the fraction in (1) can be perceived literally and the multiplication of all components $x_1\cdot ...\cdot x_{2n+1}=g^m$. can be put outside the brackets. Now, $П\left(X\right)=g^m\sum _{k=0}^n\sum _{\left\{i_1,...i_k\right\}\subset \left\{1,...,m\right\}}\left(t_{i_1}-1\right)...\left(t_{i_k}-1\right)$, where $t_j=1/x_j$, and the term of the outer sum, corresponding to $k=0$, equals 1, and the vector T = = (t₁,..., t_m) possesses the following properties:

1) t₁ ≠ t₂;

2) among t₁,..., t_m no more than n units equal 1;

3) the vector T delivers the function $\Theta \left(T\right)=\sum _{k=0}^n\sum _{\left\{i_1,...i_k\right\}\subset \left\{1,...,m\right\}}\left(t_{i_1}-1\right)...\left(t_{i_k}-1\right)$ the minimum at the set of vectors, which have $t_j\ge 1$, and $t_1\cdot ...\cdot t_m=r^m>1$, where $r=1/g$.

Let us be view Θ (T) as the function of t₁, t₂ at constancy of the other variables. Separating the terms and co-multipliers, containing variables t₁, t₂, expressed by Θ (T) one can convert them to

 

$\Theta \left(T\right)=C_2{t}_1{t}_2+\left(C_1-C_2\right)\left(t_1+t_2\right)+C_0$, (15)

 

where coefficients C₁, C₂, C₀ are not dependent on t₁, t₂, and

 

$C_1=\sum _{k=0}^{n=1}\sum _{\left\{i_1,...i_k\right\}\subset \left\{3,...,m\right\}}\left(t_{i_1}-1\right)...\left(t_{i_k}-1\right)$, $C_2=\sum _{k=0}^{n-2}\sum _{\left\{i_1,...i_k\right\}\subset \left\{3,...,m\right\}}\left(t_{i_1}-1\right)...\left(t_{i_k}-1\right)$. (16)

 

For further work, the signs of coefficients in (16) are significant at t₁·t₂ and t₁+ t₂. In the sum for C₂ all the terms are non-negative, with one of them being equal to 1. It means, C₂ > 0. Let us prove that C₁ – C₂ > 0. In accordance with (16) the outer sum for C₁ differs from the outer sum for C₂ on additional term with the number k = n –1. Therefore,  as the sum of non-negative terms. Let us assume that this sum equals 0. Then all the variables are equal to 0, i.e. any multiplication of , where , is equal to 0. Thus among the subtractions and  there are no more than n–2 that are different from 0, and it means there are at least 2n –1– (n–2) = n+1 equalling 0. Or, which is the same, among the components t₃,...,t_m there are n+1, equalling 1. It is especially true for a full set of components t₁, ..., t_m. However, this contradicts the above-mentioned property 2) of the vector T. So, C₁ – C₂ > 0.

Now, let us change t₁ and t₂ leaving the rest of the variables constant. Then the multiplication t₁t₂ = r ^m/(t₃∙...∙t_m) will also be constant, meaning in the expression (16) only the second term will be changed, which equals (with the precision of up to the positive multiplier) t₁+c/t₁, where c = r ^m/(t₃∙...∙ t_m). The sum t₁+c/t₁ acquires the minimal value at  [14]. But then as well, i.e. . Meanwhile, as to the assumption,, it means we have found the vector different from the initial one, at which the function  acquires the lesser value. This contradicts the assumption that the initial vector delivers the function Θ the minimum.

Returning to the initial variables $x_1,...,t_m$, we obtain the statement (*). Indeed, the vector that has not all components equal to each other, is not a vector which delivers the function $\Pi$(X) minimum. But this vector does exist, and it means that this is a vector having different components. And this is nothing more like the vector G. Thus the collective inequality has been proved.

Let us add that due to the well-known properties of the power scale of averages [15], it additionally follows from this inequality that the collective average is no less than any power mean with non-positive value.

The notions of the collective average and collective inequality introduced here provide simplified lower bound assessment of the quality of decisions by the non-homogeneous group. The probability of its correct decision is no less than that of the homogeneous group comprising the same number of experts, where the probability of the correct individual decision by one expert equals the geometric mean of similar probabilities in the initial non-homogeneous group.

CONCLUSION

The expressions (6, 11, 12 и 14–16) fully resolve the issue stated to determine the probability of the right majority made decision, with the assumptions accepted. The asymptotic representation and two-sided assessment, which, characterise the speed of tending towards the right decision.

For a non-homogeneous group, the existence and uniqueness of the concept of collective average as an averaged characteristic were introduced and firmly proved, which can be used to replace an individual probability of each group member, whereby preserving the probability of correctness of the collective decision

Potential applications of the results obtained can be the quantitative evaluation of election procedures and the solution of problems associated with improving the reliability of recognition of weak signals of control sensors in various transport systems, including high-speed transport systems on magnetic suspension [16-17].

About the authors

Konstantin E. Voevodskii

St. Petersburg State University

Email: kv5832@mail.ru
ORCID iD: 0000-0002-0519-5527
SPIN-code: 2579-7541

Ph.D., assistant professor

Russian Federation, 7/9, Universitetskaya embankment, Saint-Petersburg, 199034

Vladimir M. Strepetov

Emperor Alexander I St. Petersburg State Transport University

Author for correspondence.
Email: strepetovvm@mail.ru
ORCID iD: 0000-0002-4072-4519
SPIN-code: 4649-2141

Ph.D., assistant professor, Department "Theoretical Foundations of Electrical Engineering"

Russian Federation, 9 Moskovsky ave., St. Petersburg, 190031

References

Supplementary files