Wikipedia:Reference desk/Archives/Mathematics/2012 October 31

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 31

limit percentage of no duplicates drawing half...

Let P(2n) be the probability that drawing from a bag of 2n distinct items n times with replacement will not draw the same item twice... Is the limit of P(2n) as n goes to infinity zero or something positive? I think it should be zero, since if n is a 500, then the probability is 501/1000 times 502/1000 times ... 999/1000 of which there are 166 entries less than 2/3 and none greater than 1 so P(2*500) < 2^166/3^166 which is pretty small... But I'm not sure what a formal proof would look like, pick an epsilon, get k so that (2/3)^k < epsilon and then use n=3k?Naraht (talk) 03:07, 31 October 2012 (UTC)

This is basically the birthday problem. You are correct that the probability of no repeats goes to zero if the number of draws is linear in the number of objects, and the strategy you suggest for proving it will work. You have a product $\prod _{i=1}^{n}(n+i)/2n$, and over 1/4 of the terms are less than 2/3, so the product is less than (2/3)^n/4, which goes to zero. In fact, if there are k objects you only need on the order of √k draws to have high probability of a repeat. Rckrone (talk) 04:13, 31 October 2012 (UTC)

• You can get $n^{2n}$ different sequences as a result, each equally probable, ${(2n)}^{\underline {n}}={\frac {(2n)!}{(2n-n)!}}={\frac {(2n)!}{n!}}$ of which are sequences without repetition (see Permutation#Counting sequences without repetition). The probability of getting such a sequence is a ratio of the two values $P(2n)={\frac {\ \ {\frac {(2n)!}{n!}}\ \ }{n^{2n}}}={\frac {(2n)!}{n!\ n^{2n}}}$. The Stirling's approximation will be probably helpful in showing that P converges to zero as n grows indefinitely. --CiaPan (talk) 09:46, 31 October 2012 (UTC)
  Or one can easily show that ${\frac {P(2(n+1))}{P(2n)}}={\frac {2(2n+1)}{{\left(1+{\frac {1}{n}}\right)}^{2n}\,(n+1)^{2}}}\approx {\frac {4}{e^{2}\,n}}$ for large n, so P converges to zero faster than any geometric sequence. --CiaPan (talk) 11:09, 31 October 2012 (UTC)

Thank you for the information, I wasn't looking for rate to zero, but I'm glad that information is available as well...

Related Problem

OK, new related problem. Let f be defined as a function of n. Let P(k,n) be defined as the probability of drawing k items from a bag with n items in it with replacement without drawing a duplicate. For example, if f(n)=b*n for a constant b less than 1, then the limit of P(f(n),n) is zero, if on the other hand f(n)= c, then the limit of P(f(n),n) is one. So, if the limit of P(f(n),n) as n goes to infinity is a constant m where 0<m<1, what do we know about f(n)? Is it log, a square root or something like n^(1+epsilon)?)

Apply same reasoning and you'll get ${\frac {n!}{(n-k)!\,\cdot \,k^{n}}}=m.$ I'm afraid it is pretty hard to solve for k... But if you do, k(n) with m as a parameter will be your f. --CiaPan (talk) 12:01, 2 November 2012 (UTC)

Yeah. I can see that it is relatively ugly. Thanx.Naraht (talk) 17:32, 2 November 2012 (UTC)

f(n) is on the order of square root of n, as the birthday problem article mentions. More specifically they claim $f(n)\approx {\sqrt {-2n\ln(m)}}$. Also I think the expression above should be ${\frac {n!}{(n-k)!\,\cdot \,n^{k}}}=m.$ Rckrone (talk) 06:04, 3 November 2012 (UTC)

Can Obama win?

The United States is the only current example of an indirectly elected executive president, with an electoral college comprising electors representing the 50 states and the federal district.

Suppose you are GOD. Suppose you know the true probability of Obama winning in all states and the federal district. Please note that you only know the true probability for each state (and federal district) and not if he will definitely win.

How do you calculate the chances of Obama retaining his office. For example: State A is 40%. State B is 60%, etc etc 220.239.37.244 (talk) 09:13, 31 October 2012 (UTC)

See Electoral College (India) for another instance.

If you know the probabilities for each vote and they are independent then it is quite easy to get an overall probability though a trick is needed. I'll illustrate with just three voters A B C who have probabilities .1 .6 and .7 of voting yes. The total probability of 2 or more yes votes is the sum of each individual possible overall vote that has 2 or more yes votes. For instance A ye, B yes, C no would give 2 votes and the probability of that combination is .1×.6×(1-.7)=0.018. For this problem the overall chance of 2 or 3 ves votes is (.1×.6×(1-.7)) + (.1×(1-.6)×.7) + ((1-.1)×.6×.7) + (.1×.6×.7) = 0.466

For the american president doing the sums that way would take an awful long time and even the fastest computers nowadays couldn't do it before the sun engulfed the earth. However there is a nice simple way of doing the job. We calculate the probability of each total yes votes adding one elector at a time. Suppose we have calculated the probability of 0, 1 or 2 yes votes for A and B above then when we add C the probability of 1 total yes vote is the sum of the probability of 1 so far times a no by C plus the probability of 0 yes votes so far time a yes by C. Doing the sums this way the whole business can be done by a computer before your finger has raised from the enter key.

There is a problem with the original supposition however, i.e. if I were God. That is a false assumption therefore I can prove anything from it. Dmcq (talk) 10:13, 31 October 2012 (UTC)

You can also write down a generating function f(x) that has as its coefficient of x^n the probability of winning n electoral college votes

$f(x)=\prod _{j=1}^{50}\left[1-p_{j}+p_{j}x^{n_{j}}\right]$

where the product over the j is over all States, $p_{j}$ is the probability of winning state j and $n_{j}$ is the number of electoral college votes you win if you win state j. Count Iblis (talk) 18:33, 31 October 2012 (UTC)

Thank you. I think I got it. for example: Ohanian (talk) 08:53, 1 November 2012 (UTC)

It is important here to realize where the simplification comes from. Mathematica is now doing the heavy lifting, so you may think that computing f(x) is done by expanding out all the factors but that is then equivalent to the direct method, so it may look like there is no real gain in computing f(x). However, this is not the case. The efficient way to compute f(x) is to compute the series expansion of Log[f(x)], this is the sum of the series expansion of the logarithms of the individual factors, which you only need to compute to the required order. Then one can compute the exponential function of that series expansion. This only requires a small number of squarings and multiplications. But Mathematica uses an even more efficient algorithm to do this.

Functions of series expansions can usually be most efficiently computed by making use of the following algorithm for division. For given y, computing x = 1/y can be considered as solving the equation

y - 1/x = 0, if you do that using Newton-Raphson, you get the successive approximants as x_{n+1} = 2 x_{n} - y x_{n}^2. The point of this is that there is no division involved in this, only multiplication. In each step the number of significant digits are squared. Now, if y is a polynomial, then this algorithm yields the series expansion if 1/y, and in each step you are doubling the number of correct expansion coefficients.

To compute the series expansion of Log[y(x)], you can use the above algorithm to compute y'(x)/y(x) and integrate term by term. The most efficient way to compute s(x) = exp[y(x)] is to solve the equation

log[s(x)] = y(x) using Newton-Raphson, so this is then a nested Newton-Raphson as computing the logarithm also requires using Newton-Raphson. But this is still much more efficient than computing exp[y(x)] directly. This then allows you to compute the series expansion of any elementary function as you can write them as compositions of logarithms and exponential functions. Count Iblis (talk) 16:24, 1 November 2012 (UTC)

Another shortcut you can take is to consider "solid Obama states" and "solid Romney states" to be out of play, since the chance of an upset in those is virtually 0. This reduces the number of swing states (and swing electoral votes, for states lacking the winner-take-all rule) to a small enough number that every possible combo can be considered. For example, if you end up with 20 swings states and electors, that's 2²⁰, or a bit over a million, calculations, which is simple for a computer to do. Just plug in the probability of a Romney or Obama win for each, and run the numbers to get the total probability. For example, this map shows only 16 states which aren't strongly for one candidate or the other: [1]. StuRat (talk) 18:44, 31 October 2012 (UTC)

• It's easy to calculate the expected value of Obama's total, and its variance. Those should give a decent approximation of his probability of winning. If that isn't good enough, I would probably do this using a Monte Carlo method -- run a million or so simulated elections on a computer, and count how many of them Obama wins. Looie496 (talk) 19:03, 31 October 2012 (UTC)

Based on info easily found on the internet. Obama seems to have a 62% chance of wining the election. Ohanian (talk) 00:37, 4 November 2012 (UTC) File:Obama wining 20121104.png

I don't think the hypothesis that all those probabilities are independent is realistic. Polling results have ups and downs that are highly correlated between states. Fivethirtyeight.com is the best known probability forecast site, that has been in the news a lot recently, and it currently puts Obama at over 80%. 67.119.3.105 (talk) 08:41, 4 November 2012 (UTC)