Wikipedia:Reference desk/Archives/Mathematics/2008 August 4

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.

August 4

Raffle winning strategy

We're having a raffle at work. Each prize has a jar associated with it. You buy tickets and put your tickets in the jar for the prize that you'd like to win. Four of the prizes are vacation time. So, which option gives me better chances of winning at least one of the vacation time prizes, A) putting all my tickets into a single jar or B) spreading my tickets over all four jars? Let's assume that I can only win one of the vacation prizes and let's assume that all four jars are equally filled with other people's tickets. Dismas|^(talk) 02:56, 4 August 2008 (UTC)

Say each of the jars has N tickets, and you have 4. If you put all four in the first jar, the probability you win is 4/(N+4). If you put one in each jar, the probability that you lose is (N/(N+1))^4, so the probability that you win is 1 - (N/(N+1))^4. For any positive N, the latter probability is greater, so you should spread your tickets over all the jars. However, as N increases, the difference between the two strategies decreases, and in the limit of large N, they are the same. So if there are a lot of other people, it would probably be a better strategy to guess which jar has the fewest tickets, and put all your tickets in that one. —Keenan Pepper 04:21, 4 August 2008 (UTC)

(Edit conflict, and we've said almost exactly the same thing, but I'll post mine anyway!) Ok, let's assume you buy four tickets, and there are n other tickets in each jar. If you put all your tickets in one jar, your chance of winning is simply ${\frac {4}{n+4}}$ (you have 4 tickets and there are n+4 tickets in the jar). If you put one ticket in each jar, your chance of winning at least one prize is one minus the chance of winning no prizes, in other words $1-\left({\frac {n}{n+1}}\right)^{4}$ (the chance of losing each jar is ${\frac {n}{n+1}}$, and there are 4 jars, so the chance of losing all of them is $\left({\frac {n}{n+1}}\right)^{4}$). I then plugged those formulae into a maths computer package and found that putting 1 in each jar is better for any value of n, although the difference becomes very small as n gets very large. The difference is at most 14% for n=1 and drops below 1% for n>20. So, my advice would be to put them in different jars if there are only a few tickets in each, otherwise put them all in the one with the least tickets (obviously, that requires you to play last, but I'm sure you can manage that if you try!). --Tango (talk) 04:24, 4 August 2008 (UTC)

Tango's maths computer may be replaced by the binomial series

$1-\left({\frac {n}{n+1}}\right)^{4}=1-(1+n^{-1})^{-4}=1-\sum _{i=0}^{\infty }{{-4} \choose i}n^{-i}={\frac {4}{n}}-{\frac {10}{n^{2}}}+{\frac {20}{n^{3}}}-\cdots$

${\frac {4}{n+4}}=1-(1+4n^{-1})^{-1}=1-\sum _{i=0}^{\infty }{{-1} \choose i}4^{i}n^{-i}={\frac {4}{n}}-{\frac {16}{n^{2}}}+{\frac {64}{n^{3}}}-\cdots$

So

$1-\left({\frac {n}{n+1}}\right)^{4}-{\frac {4}{n+4}}={\frac {6}{n^{2}}}-{\frac {44}{n^{3}}}+\cdots$

confirming the behavior for big values of n. Bo Jacoby (talk) 08:35, 4 August 2008 (UTC).

Thanks! I split the tickets amongst the jars. We'll see how I did tomorrow... Dismas|^(talk) 09:58, 4 August 2008 (UTC)

Absolutely, it just seemed quicker to get the computer to do it! Obviously not quite quick enough, though, by 3 minutes! Also, the computer told me the two formulae didn't switch places at any point before n got large enough to make it all simple - that could also be done analytically, of course, but I didn't see the point. --Tango (talk) 21:59, 4 August 2008 (UTC)

Thanks for the help all! I didn't any of the vacation time. Though I did put a ticket in the jar for a pair of hand knitted mittens and hat. I'm going to save them for winter and give them to my wife.  :-) Dismas|^(talk) 14:11, 7 August 2008 (UTC)

Poisson Distribution

I am trying to do this question, but getting bogged down in sums of factorial fractions.

Y is the number of calls received in one hour, and it has a Poisson(20) distribution. Given Y=y, each of the y calls is redirected with probability 0.2. If X is the number of redirected calls, show that X~Poisson(4).

I have taken exp(-20) out the front of an infinite sum over i of 1/(i-j!)i! multiplied by 16^j multiplied by (1/4)^i. I can see where I need to get - the infinite sum of (16^j)/j! needs to come out the front, and then we need to somehow wind up with a 4^i/i! out of what is left. I don't really understand how to manipulate the factorial fractions to get there. help, please! —Preceding unsigned comment added by Damian Eldridge (talk • contribs) 06:19, 4 August 2008 (UTC)

For a fixed j, you need to calculate that sum. It would help if you make the substitution $k=i-j$. Oded (talk) 11:33, 4 August 2008 (UTC)

Thankyou! Now I see how easy it actually is. I'll remember that tip for sure. —Preceding unsigned comment added by Damian Eldridge (talk • contribs) 01:08, 7 August 2008 (UTC)

Looking for Simon Plouffe's magical formulae

I'm looking for Simon's magical formulae that produces the digits of Pi in base 10 without first calculating the preceeding digits.

I know for sure that this formulae exists because it said so in Wikipedia.

On Simon's page Simon Plouffe, it says "Plouffe discovered an algorithm for the computation of π in any base in 1996. He has expressed regret for having shared credit for his discovery of this formula with Bailey and Borwein.".

Any idea where is the formulae for base 10? 122.107.146.22 (talk) 09:13, 4 August 2008 (UTC)

An algorithm that can compute digits of a mathematical constant without using preceeding digits is called a spigot algorithm. There is a well-known spigot algorithm for π called the Bailey–Borwein–Plouffe formula, but this calculates hexadecimal (or, equivalently, binary) digits of π, not decimal digits. I am not aware of a decimal spigot algorithm for π. As far as a decimal spigot algorithm is concerned, this page says "Plouffe, for one, has found a way to compute individual decimal digits of pi without calculating preceding digits. That makes it possible to compute a particular decimal digit of pi using a pocket calculator, Plouffe says. However, his algorithm is fairly slow and clearly impractical for determining the millionth or billionth decimal digit of pi." It gives another link here, which I haven't checked. I don't understand the comment about efficiency, because I would have thought a spigot algorithm should be more or less equally efficient whether it is calculating the millionth, billionth or just the tenth digit - that is kind of the point of spigot algorithms. Gandalf61 (talk) 10:21, 4 August 2008 (UTC)

Hmm. The latter article appears to have moved to http://www.lacim.uqam.ca/~plouffe/Simon/articlepi.html, the link in the first is broken. GromXXVII (talk) 11:01, 4 August 2008 (UTC)

Fabrice Bellard lists this approach for any base, from 1997. It's a slight improvement over Plouffe's 1996 formula in that it runs in O($n^{2}$) time rather than his O($n^{3}\log \left(n\right)^{3}$). --_{tiny plastic} Grey Knight ⊖ 16:22, 4 August 2008 (UTC)

Here's Simon Plouffe's paper http://arxiv.org/ftp/arxiv/papers/0912/0912.0303.pdf Here's Fabrice Bellard's improvement http://bellard.org/pi/pi_n2/pi_n2.html#plo96

confusing problem

explanation: ok, so I guess I should make this clear first off, this isn't homework. Thankfully I stopped having to do math homework quite a few years ago... yet for some reason a part of my brain keeps coming up with these problems that the rest of me is usually completly mentally unequipped to answer. They're just little thought experiments that I come up with by accident that bug me until I work them out (or more usually get someone else to do it for me). This is one of those problems, and I would be most grateful if someone could help me out here before I go completely insane.

The only way I can think about the problem without my brain melting is in high-school esque math problem terms, imagining actual physical objects and properties (balls, boxes, colors). I don't know if that's clear enough but seeing as I know nothing about actual mathematics this is the best I can do. Hopefully it can be translated into proper math speak.

problem: You have a number of balls of different colors. The number of colors is X. There an equal number of balls of each colour. This amount of balls of each color is Y. There is also an indeterminate amount of boxes that can hold the balls. However each box can only contain a certain number of balls, no more and no less. The number of balls each box can contain is Z. In addition, no box can contain more than one ball of the same colour; and no two boxes can ever have the same combination of coloured balls.

The questions that are bugging me are: for what combinations of values for X, Y and Z is it possible to put all of the balls into boxes without any left over balls? And for these combinations, how many boxes are needed?

The answer can be in an algebraic equation, I think I can get my head around that. However if this problem unknowingly steers into some really complex math stuff, a little explanation might be necessary. Thanks :)

--86.146.162.73 (talk) 15:12, 4 August 2008 (UTC)

I don't know the answer and I haven't attempted to think about it, but start by looking under combinatorial design both here and on Google. And Google Scholar and Google Books. Michael Hardy (talk) 16:20, 4 August 2008 (UTC)

Why not start with small cases to get an idea? What happens with (X,Y,Z)=(1,1,1)? (2,1,1)? (2,2,1)? - Rainwarrior (talk) 16:37, 4 August 2008 (UTC)

The problem sounds equivalent very closely related to the generation of balanced incomplete block designs. The key word here is "incomplete": not every color will be in every box. That page seems somewhat obtuse but it might be a good start. I would also recommend Google searches, per MH above. Baccyak4H (Yak!) 17:30, 4 August 2008 (UTC)

Thanks for the help but as I suspected, this goes into territory that is completely beyond my ken. Perhaps I should have been more clear about my complete lack of aptitude; I can barely do multiplication in my head (I suspect I suffer from dyscalculia, but I've never been diagnosed). I don't understand anything in the above article past "in". I really don't know why I torture myself by coming up with questions like this :p I think I'm going to try Rainwarrior's idea instead and work it out graphically in MS Paint or with colored boxes in Excel or something. --86.146.162.73 (talk) 17:57, 4 August 2008 (UTC)

I know for a fact that there are tables of sets of {X, Y, Z} out there (I used them in grad school...), but I do not have any refs on hand. They are likely older ones—this topic has lost some of its research luster, as the main reason it was studied was to avoid doing more complicated matrix operations by hand before cheap computing was available.

That said, per RW it should not be too hard to enumerate the smaller examples. Keep in mind the necessary restrictions: you have assumed that Z<X, since otherwise some boxes would have more than one ball of a given color. Also, from that article (rewritten slightly):

(# boxes) × Z = X × Y (equiv to the bk=vr expression)

The other expression in that article states a restriction which I am not sure is required by your conditions.

Baccyak4H (Yak!) 18:33, 4 August 2008 (UTC)

(unindenting) Is this so hard as all the posters indicate? I get X*Y/Z<=X!/Z!(X-Z)! and in addition X*Y/Z must be integer. Taemyr (talk) 04:10, 5 August 2008 (UTC)

That doesn't work. Try X=1, Y=2, Z=2. It satisfies your condition, but still fails because of the "no two boxes can ever have the same combination of coloured balls" condition. --Tango (talk) 04:16, 5 August 2008 (UTC)

Actually, your counterexample isn't a counterexample (provided X!/Z!(X-Z)! is understood as a binomial coefficient). The maximum number of boxes used is the binomial coefficient X choose Z, denoted $\scriptstyle {\binom {X}{Z}}$, since this is the number of possible distinct combinations of X colors into sets of size Z. The total number of balls XY must not exceed $\scriptstyle {{\binom {X}{Z}}Z}$, since otherwise there will be balls left over. In addition, XY/Z must be an integer since the total number of balls must be divisible by the box size (each box, if used, must be completely filled). Now, these two conditions are obviously necessary, but I can't see a proof that they are also sufficient, although it seems quite plausible. siℓℓy rabbit (talk) 13:24, 5 August 2008 (UTC)

Good point - my example is a degenerate case and doesn't really prove anything. I agree necessity is obvious, sufficiency is more of a problem, though. I suspect there may be a tighter bound on the total number of balls, although I haven't even tried looking for one yet. It won't be anything simple, since that bound can be attained in some trivial cases (eg. (1,1,1)). --Tango (talk) 09:22, 6 August 2008 (UTC)

Is there a formula for the probability of rolling a sum? given a pair of 6-sided dice?

In other words, is there some neat little algebra formula that I can just plug in?

Like the odds of rolling a 7 is .166(repeating) percent and the odds of rolling a 2 or 12 are both .0277(repeating)

in other words, is there an equation like f(x) = y

The odds of rolling a 10 can be either 6+4, 5+5, 4+6 thus f(10) = .0833333

Is there a algebraic or statistical formula that I can relate the input variable to the output formula?

I know that the answer is yes, if the function is continuous, but this dice problem is a stepwise function. (the derivative doesnt exist, thus you can't use calculus to come up with the equation)

Is there a catchy formula for this simple phenomenon? I've checked the dice page and the binomial page and used google search exclusively on en.wikipedia.org Sentriclecub (talk) 16:11, 4 August 2008 (UTC)

The probability that the sum is x is

${\frac {6-|x-7|}{36}}.$

I don't find that very "catchy", the way most identities in probability that you see displayed here are. That's probably why you don't see it. Michael Hardy (talk) 16:17, 4 August 2008 (UTC)

You might be able to derive a catchy expression by viewing the problem as one of counting partitions of x into n parts (in your case n=2) where the partition sizes are restricted to be no greater than six. That would be the numerator and 6ⁿ would be the denominator. The restriction to be no greater than six might make the general derivation tricky, however. Baccyak4H (Yak!) 17:51, 4 August 2008 (UTC)

Excellent, I saw that too, that the sum goes 1,2,3,4,5,6,5,4,3,2,1 all over 36. I was squaring and then taking the sq-root, but using simple absolute value operators is much more aesthetic. Sentriclecub (talk) 19:07, 4 August 2008 (UTC)