From: Stephen Montgomery-Smith Subject: Re: Which distribution is this... Date: Thu, 28 Dec 2000 19:56:21 GMT Newsgroups: sci.math Summary: [missing] The problem you are looking at is this - let a_1, a_2, ..., a_n be a sequence of numbers, and let e_1, e_2, ..., e_n be independent random variables that take 0 or 1 with probability 1/2. So you are interested in the distribution of S' = sum a_k e_k This is related to the following problem - let r_1, r_2, ..., r_n be independent random variables taking 1 or -1 with probbility 1/2. Then S = sum a_k r_k is related to S' via S = 2S' - sum a_k. The quantity S is often called a Radermacher sum (the r_k being called a Rademacher variable). Sometimes they are also called Bernoulli sums. These random variables have many applications in analysis via the famous Khinchine inequalities. Exact formulae for the distribution are hard to come by, but a couple papers independently obtained approximatie formulae: Montgomery, H.L., Odlyzko, A.M. (1988) Large deviations of sums of independent random variables, Acta Arithmetica} 49, 427--434. Montgomery-Smith, S.J. (1990) The distribution of Rademacher sums. Proc. Amer. Math. Soc. 109, 517--522. (The similarity of the last names is completely coincidental.) For more general problems I have a recent paper "Measuring the magnitude of sums of independent random variables" joint with Pawel Hitczenko which you can get off my web page: http://www.math.missouri.edu/~stephen/preprints/ Derek Ross wrote: > > This is an odd distribution... I think it may somehow be related to the > binomial distribution, but I'm not certain. > > The idea is difficult to explain, so here's a "real-life" example of > generating the distribution: > > I have four coins in my hand. Each coin has a number on both sides. All > coins have a zero on one side, and the other side has a number from 1 to 4. > > I then hurl the handful of coins at the ground, then add up the values of > all the coins. > > Here's a list of every possible combination of ways the coins may land, with > the corresponding total. > > Coins Total > 0 0 0 0 0 > 1 0 0 0 1 > 0 2 0 0 2 > 1 2 0 0 3 > 0 0 3 0 3 > 1 0 3 0 4 > 0 2 3 0 5 > 1 2 3 0 6 > 0 0 0 4 4 > 1 0 0 4 5 > 0 2 0 4 6 > 1 2 0 4 7 > 0 0 3 4 7 > 1 0 3 4 8 > 0 2 3 4 9 > 1 2 3 4 10 > > If you plot the histogram, you can see the faint shadow of a bell curve > there. > > Histograms of totals: > Total Quantity > 0 1 > 1 1 > 2 1 > 3 2 > 4 2 > 5 2 > 6 2 > 7 2 > 8 1 > 9 1 > 10 1 > > Well then, with all that being said, my question: what kind of distribution > is this anyway? I know I can calculate everything by hand for a small number > of coins, but say I had 100 coins, then I would need an equation to generate > the distribution. > > Any help would be greatly appreciated... > > Derek Ross. -- Stephen Montgomery-Smith stephen@math.missouri.edu http://www.math.missouri.edu/~stephen ============================================================================== From: "Peter L. Montgomery" Subject: Re: Which distribution is this... Date: Fri, 29 Dec 2000 06:06:48 GMT Newsgroups: sci.math In article <%TL26.59365$Z9.3668571@news1.rdc1.mb.home.com> "Derek Ross" writes: >This is an odd distribution... I think it may somehow be related to the >binomial distribution, but I'm not certain. >The idea is difficult to explain, so here's a "real-life" example of >generating the distribution: >I have four coins in my hand. Each coin has a number on both sides. All >coins have a zero on one side, and the other side has a number from 1 to 4. >I then hurl the handful of coins at the ground, then add up the values of >all the coins. >Here's a list of every possible combination of ways the coins may land, with >the corresponding total. >Coins Total >0 0 0 0 0 >1 0 0 0 1 >0 2 0 0 2 >1 2 0 0 3 >0 0 3 0 3 >1 0 3 0 4 >0 2 3 0 5 >1 2 3 0 6 >0 0 0 4 4 >1 0 0 4 5 >0 2 0 4 6 >1 2 0 4 7 >0 0 3 4 7 >1 0 3 4 8 >0 2 3 4 9 >1 2 3 4 10 >If you plot the histogram, you can see the faint shadow of a bell curve >there. >Histograms of totals: >Total Quantity > 0 1 > 1 1 > 2 1 > 3 2 > 4 2 > 5 2 > 6 2 > 7 2 > 8 1 > 9 1 > 10 1 >Well then, with all that being said, my question: what kind of distribution >is this anyway? I know I can calculate everything by hand for a small number >of coins, but say I had 100 coins, then I would need an equation to generate >the distribution. From your histogram, form the generating function, in which the coefficient of X^j is the number of ways to get a total of j: F(X) = 1 + X + X^2 + 2X^3 + 2X^4 + 2X^5 + 2X^6 + 2X^7 + X^8 + X^9 + X^10 This factors as F(X) = (1 + X)^2 * (1 + X^2) * (1 - X + X^2) * (1 + X^4). It looks more recognizable if we write it as F(X) = (1 + X)*(1 + X^2)*(1 + X^3)*(1 + X^4) If you add a fifth coin with 0 and 5 on its sides, you need to multiply this product by 1 + X^5. In terms of your histogram, you shift the existing entries up 5 and add them to what you have now: (1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0) + (0 0 0 0 0 1 1 1 2 2 2 2 2 1 1 1) = (1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1) A coin with sides 0 and n has average value n/2 and variance n^2/4. When you have 5 coins, with non-zero sides being 1, 2, 3, 4, 5, the average sum is (1 + 2 + 3 + 4 + 5)/2 = 7.5 and the variance is (1 + 4 + 9 + 16 + 25)/4 = 13.75. The standard deviation is about sqrt(13.75), or 3.71. Indeed, the sum is in [4, 11] (one standard deviation from 7.5) with probability 22/32 = 0.6875 . EXERCISE: How many ways can one exchange a US dollar (100 cents) for an equivalent amount of coinage, using standard denominations (1, 5, 10, 25 cents)? -- Can't decide between Gore and Bush? Elect them both. A Gore-Bush-ship sounds like Gorbachev. Peter-Lawrence.Montgomery@cwi.nl Home: San Rafael, California Microsoft Research and CWI