Suppose that in an election, candidate A receives votes, while candidate B receives votes, where . Assuming that votes are counted in random order, what is the probability that during the whole process of counting A will be ahead of B?
Solution
Note that other votes, if any, do not matter, and we may assume that is the total number of votes. The process of counting votes is determined by the arrangement of the votes, that is, the arrangement of symbols A, and symbols B. Clearly, such an arrangement is uniquely determined by specifying the locations of the As (or, equivalently, Bs). It might be helpful to use a graphical representation: define the function as the net count for candidate A after inspection of votes. Thus, if in the first votes, we had votes for A and votes for B, then . We can then represent the process of counting as a polygonal line that starts at the origin and has vertices (see Figure 3.2).
In Figure 3.2, we have the beginning of counting, when the first five votes inspected are AABAB. The problem can now be formulated as finding the probability that the counting function lies above the ‐axis for all . Observe that the first vote counted must be for A (as in Figure 3.2); this occurs with probability .
The remaining votes will give a polygonal line leading from to , and we must find the number of such lines that will never touch or cross the ‐axis. The number of such lines is equal to the total number of lines from to minus the number of lines from to which touch or cross the ‐axis. The total number of lines leading from to is , since each such line has steps “up” and steps “down,” which can be ordered in any manner. Thus, it remains to count the number of lines from to that touch or cross the ‐axis. Let be the set of all such lines. Each line in must touch the ‐axis for the first time at some point, say (see Figure 3.3). If we reflect the part of this line that lies to the left of with respect to ‐axis, we obtain a line leading from to . Moreover, different lines in will correspond to different lines leading from to and each line in the latter set will be obtained from some line in . This means that the set СКАЧАТЬ
