Probability and Statistical Inference. Robert Bartoszynski

Probability and Statistical Inference

target="_blank" rel="nofollow" href="#fb3_img_img_ee96b2e9-934b-5307-b73b-803f6f8303f0.png" alt="images"/> denote the probability of the intersection of images

events,

Clearly, the numbers of terms in the consecutive sums are

and

(3.25) equation

To evaluate images we can argue as follows: Assume that the envelopes are ordered in some way. The total number of ways one can order images letters is images . If specific images events, say images are to occur (perhaps in conjunction with other events), then the letters number images must be at their appropriate places in the ordering (to match their envelopes). The remaining images letters can appear in any of the images orders. Thus,

Consequently, the images th term in the sum (3.25) equals (up to the sign)

and we obtain

Since

we have

with the accuracy increasing as images . The approximation is actually quite good for small images . The limiting value is 0.63212056, while the exact values of the probability images of at least one match for selected values of images are

Example 3.12 Ballot Problem

Suppose that in an election, candidate A receives images votes, while candidate B receives images votes, where images . 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 images is the total number of votes. The process of counting votes is determined by the arrangement of the votes, that is, the arrangement of images symbols A, and images 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 images as the net count for candidate A after inspection of images votes. Thus, if in the first images votes, we had images votes for A and images votes for B, then images . We can then represent the process of counting as a polygonal line that starts at the origin and has vertices images (see Figure 3.2).

Graph representing the process of counting votes, depicted as a polygonal line that starts at the origin and has vertices (k,C(k)), k = 1, . . . , a + b.

Figure 3.2 Process of counting votes.

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 images lies above the images ‐axis for all images . Observe that the first vote counted must be for A (as in Figure 3.2); this occurs with probability images .

Graph representing the reflection principle, depicting a number of lines from (1, 1) to (a + b, a − b) that touch or cross the x-axis. Reflecting the part of this line that lies to the left of t with respect to x-axis, we obtain a line leading from (1,−1) to (a + b, a − b).

Figure 3.3 Reflection principle.

The remaining votes will give a polygonal line leading from images to images , and we must find the number of such lines that will never touch or cross the images ‐axis.

Скачать книгу