Using the las vegas algorithm derive the expression for the

Using the las vegas algorithm, derive the expression for the number of rounds, f(n) used to elect the a president among n people

Solution

Sampling is a very common technique for estimating the fraction of elements in a set that have a certain property. For example, suppose that you would like to know how many Americans plan to vote for the Republican candidate in the next presidential election. It is infeasible to ask every American how they intend to vote, so pollsters will typically contact n Americans selected at random and then compute the fraction of those Americans that will vote Republican. This value is then used as the estimate of the number of all Americans that will vote Republican. For example, if 45% of the n contacted voters report that they will vote Republican, the pollster reports that 45% of all Americans will vote Republican. In addition, the pollster will usually also provide some sort of qualifying statement such as “There is a 95% probability that the poll is accurate to within 4 percentage points.” The qualifying statement is often the source of confusion and misinterpretation. For example, many people interpret the qualifying statement to mean that there is a 95% chance that between 41% and 49% of Americans intend to vote Republican. But this is wrong! The fraction of Americans that intend to vote Republican is a fixed (and unknown) value p that is not a random variable. Since p is not a random variable, we cannot say anything about the probability that

.41<p <.49.

Define Ri to be the indicator random variable for the ith contacted American in the sample. In particular, set Ri = 1 if the ith contacted American intends to vote Republican and Ri = 0 otherwise. For the purposes of the analysis, we will assume that the ith contacted American is selected uniformly at random (with replacement) from the set of all Americans.We will also assume that every contacted person responds honestly about whether or not they intend to vote Republican and that there are only two options—each American intends to vote Republican or they don’t. p_r[R_i=1]=p

where p is the (unknown) fraction of Americans that intend to vote Republican. We next define

T=R₁+R₂+…+R_n

to be the number of contacted Americans who intend to vote Republican. Then T /n is a random variable that is the estimate of the fraction of Americans that intend to vote Republican. We are now ready to provide the correct interpretation of the qualifying statement. The poll results mean that

p_r=[T/n-p,<0.4]>.95

In other words, there is a 95% chance that the sample group will produce an estimate that is within 4 percentage points of the correct value for the overall population. So either we were “unlucky” in selecting the people to poll or the results of the poll will be correct to within 4 points.