Wikipedia:Reference desk/Archives/Mathematics/2009 April 11

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.

April 11

Limit involving moment generating functions

Hi there - I'm looking to prove the result that if X is a real R.V. with moment generating function $m(\theta )=E(e^{\theta X})$, then if the MGF is finite for some theta > 0, $\lim _{x\to \infty }x^{n}P[X\geq x]=0\forall n\geq 0$ . I really have absolutely no clue where to start - is it central limit theorem related? I could really use a hand on this one, thanks a lot!

Otherlobby17 (talk) 06:51, 11 April 2009 (UTC)

Look at the integral that defines $m(\theta )$, namely $\int e^{\theta x}dF$. If it is finite, then $\lim _{x\to \infty }e^{\theta x}P[X\geq x]=0$, which is stronger than you need. McKay (talk) 09:14, 11 April 2009 (UTC)

Fantastic, thanks very much buddy :) Otherlobby17 (talk) 04:15, 12 April 2009 (UTC)

Graph

Is it possible for the graph of a continuous function to touch the x-axis without there being a repeated root? 92.0.38.75 (talk) 13:02, 11 April 2009 (UTC)

Are you referring to polynomial functions, rather than the less restrictive class of continuous functions? It may be my own ignorance, but I don't know the definition of a repeated root for an arbitrary continuous function. But in the case of a polynomial function, any instance where the function touches but does not pass through the x-axis must be a repeated root. To see this (assuming you have had calculus), note that the derivative at the root must be zero for the curve to just barely kiss the graph. Take the derivative first:

${\frac {d}{dx}}a_{0}(x-a_{1})(x_{a}-2)\cdots (x-a_{n})$

$=a_{0}\sum _{i=1}^{n}\prod _{k\neq i}(x-a_{k})$

If the root is $a_{b}$, the term $(x-a_{b})$ appears in every product except one (when b = i). Now set $x=a_{b}$, as well as setting the expression equal to zero (knowing that the derivative is zero at the root); all that is left is

$\prod _{k\neq b}(x-a_{1})(x_{a}-2)\cdots (x-a_{n})=0$

Ergo there must be another term $a_{c}=a_{b}$, or equivalently, the multiplicity of the root is greater than one.

Hope this helps, --TeaDrinker (talk) 15:01, 11 April 2009 (UTC)

What type of root does the absolute value function |x| have at 0? What about ${\sqrt {x}}$ at 0? I think the concept "repeated root" is only usually defined for functions with derivatives. The order of the root is the number of values f(x), f'(x), f"(x),... which are zero. McKay (talk) 01:50, 12 April 2009 (UTC)

You could extend that to say that if a function is continuous but not differentiable at a zero, then the zero has order 0, analogously to the way one sometimes thinks of continuous functions as being 0-times differentiable, or C⁰. I don't know if this is useful for anything though. Algebraist 11:44, 12 April 2009 (UTC)

What symbol is this?

Ran across this symbol in a mathematics book but I have no idea what it is, or how to type it up in LaTeX. It's a bit like a cursive capital X with a short horizontal line through the middle. My first instinct was $\Xi$ but it looks nothing like it. 128.86.152.139 (talk) 14:17, 11 April 2009 (UTC)

Hmm, I don't know anything fitting that description, but have you tried the comprehensive LaTeX symbols list? --TeaDrinker (talk) 14:23, 11 April 2009 (UTC)

I'm going through it now.  :( But it's incredibly long... 128.86.152.139 (talk) 14:36, 11 April 2009 (UTC)

What book is it? What's the context in which the symbol was used? --TeaDrinker (talk) 14:45, 11 April 2009 (UTC)

If you'd have said a vertical line, I'd have said Zhe. It's a shame you didn't. 163.1.176.253 (talk) 14:57, 11 April 2009 (UTC)

don't forget that a lot of people cross weird things. a close acquaintance crosses their v's! Maybe it's just a fancy x, so that you don't think it's a normal x?  :) 79.122.103.33 (talk) 15:49, 11 April 2009 (UTC)

Do you mean ${\mathfrak {X}}$? That's just a fraktur capital X. Algebraist 16:37, 11 April 2009 (UTC)

Brilliant, thanks. For context, my lecturer uses it to denote a set of data: ${\mathfrak {X}}=\left\{x_{1},x_{2},\dots ,x_{n}\right\}$ Is there a non-Blackletter-style font, though? 128.86.152.139 (talk) 02:34, 12 April 2009 (UTC)

how does variable-length testing work?

let's say I buy a rigged coin (slightly favors one side) but forget what side is favored

could i just write a script that i put throws into one after the other, and at each stage it tries that many with a fair coin (for example at throw #5 it throws a fair coin five times) but REPEATEDLY, a MILLION times, to see how many times the fair coin behaves the same way under that many throws, ie as a percentage.

Then if the fair coin only behaves that way 4% of the million times, then it would be 96% confident that the currently winning side is weighted?

here are real examples i just ran with a script: if at throw #10 the count is 7 heads to 3 tails (70% heads), it ran a million times ten throws and came up in 172331 of them (17%) with at least that many. So it would report 83% confidence that heads are weighted.

if at throw #50 the count is 35 heads to 15 tails (70% heads), it ran a million times fifty throws and came up in 3356 of them (0.33%) with at least that many. So it would report report 99.67% confidence heads are weighted.

#1: t

0 head 1 tails

50% conf. heads weighted



#2: t

0 heads 2 tails

50% conf. heads weighted



#3: h

1 head 2 tails

50% conf. heads weighted



...

#10: h

7 heads 3 tails

83% conf. heads weighted

...

#50:h

35 heads 15 tails

99.7% conf. heads weighted
 

is that really how statistics works? if I write my script like I intend to will it be accurate? Also how many decimal places should I show if I am running the 'monte carlo' simulation with a million throws?

Is a million throws accurate enough to see how often a fair coin behaves that way, or should I up it to a billion or even more? could i use a formula, and if so what? (i dont know stats).

Thanks! 79.122.103.33 (talk) 15:30, 11 April 2009 (UTC)

The confidence interval is much tighter than that, see binomial distribution. 66.127.52.118 (talk) 20:13, 11 April 2009 (UTC)

why does modulus of a random integer in a high range favor lower answers SO SLIGHTLY?

say rand() returns 0-32767 but you want 0-100 - you can just do rand() % 100 which is pretty much an accepted programming practice but results in a very slighly skewed distribution.

data

My question is, how come the skew in the distribution is so incredibly slight?? Here I did it a million times:

0:10137
1:9967
2:10225
3:10157
4:9921
5:10096
6:10087
7:9924
8:9876
9:9994
10:10052
11:10022
12:10098
13:9940
14:10080
15:9939
16:9967
17:10067
18:9930
19:10058
20:10072
21:9882
22:9940
23:9793
24:10051
25:10105
26:10079
27:9970
28:9998
29:10197
30:9868
31:9979
32:10006
33:10014
34:9991
35:10062
36:9641
37:10054
38:9938
39:10221
40:9957
41:10064
42:9913
43:9858
44:10050
45:10080
46:10010
47:10009
48:10147
49:9971
50:10107
51:10083
52:9943
53:9998
54:9926
55:10036
56:9965
57:10048
58:10130
59:10049
60:9889
61:9843
62:10067
63:9918
64:10109
65:10201
66:10037
67:10049
68:9940
69:10011
70:10061
71:9946
72:10017
73:9781
74:9946
75:9986
76:10180
77:9888
78:9850
79:10034
80:10186
81:9803
82:9948
83:10040
84:9984
85:10109
86:9986
87:10006
88:9883
89:9834
90:9921
91:10002
92:10191
93:10091
94:9990
95:9910
96:9837
97:9793
98:10097
99:9894

I barely see the effect unless I know to look for it (at 0 does come up more than 99, but then again 1 doesn't...)

Here they are as percentages of 10,000 (the actual expected number):

101.37%
99.67%
102.25%
101.57%
99.21%
100.96%
100.87%
99.24%
98.76%
99.94%
100.52%
100.22%
100.98%
99.4%
100.8%
99.39%
99.67%
100.67%
99.3%
100.58%
100.72%
98.82%
99.4%
97.93%
100.51%
101.05%
100.79%
99.7%
99.98%
101.97%
98.68%
99.79%
100.06%
100.14%
99.91%
100.62%
96.41%
100.54%
99.38%
102.21%
99.57%
100.64%
99.13%
98.58%
100.5%
100.8%
100.1%
100.09%
101.47%
99.71%
101.07%
100.83%
99.43%
99.98%
99.26%
100.36%
99.65%
100.48%
101.3%
100.49%
98.89%
98.43%
100.67%
99.18%
101.09%
102.01%
100.37%
100.49%
99.4%
100.11%
100.61%
99.46%
100.17%
97.81%
99.46%
99.86%
101.8%
98.88%
98.5%
100.34%
101.86%
98.03%
99.48%
100.4%
99.84%
101.09%
99.86%
100.06%
98.83%
98.34%
99.21%
100.02%
101.91%
100.91%
99.9%
99.1%
98.37%
97.93%
100.97%
98.94%

As you can see they're all over the place.

So I'll do it a billion times:

0:10038140
1:10008197
2:10009360
3:10006955
4:10011825
5:10010609
6:10009413
7:10006938
8:10011526
9:10010894
10:10010597
11:10009374
12:10009683
13:10007576
14:10011881
15:10009578
16:10010504
17:10009339
18:10009367
19:10010843
20:10006451
21:10006077
22:10009165
23:10014474
24:10006321
25:10006088
26:10007508
27:10007083
28:10008172
29:10009126
30:10011141
31:10011209
32:10009601
33:10011616
34:10006668
35:10008558
36:10012031
37:10011200
38:10008657
39:10011348
40:10012982
41:10012670
42:10011145
43:10008010
44:10011152
45:10009978
46:10011937
47:10010535
48:10008799
49:10006801
50:10009905
51:10009997
52:10007276
53:10012822
54:10012214
55:10005860
56:10010537
57:10010839
58:10008926
59:10011667
60:10008250
61:10012131
62:10003874
63:10005923
64:10014245
65:10009392
66:10009417
67:9982730
68:9978860
69:9980179
70:9978155
71:9982744
72:9977599
73:9976077
74:9981662
75:9977978
76:9982794
77:9981410
78:9982701
79:9978788
80:9977564
81:9980187
82:9980063
83:9976760
84:9980559
85:9978017
86:9980910
87:9981715
88:9978261
89:9981133
90:9979202
91:9976322
92:9977249
93:9976058
94:9977878
95:9984202
96:9980344
97:9981362
98:9978432
99:9979728

the effect becomes clear... however it is TINY!!!

Here they are as percentages (of the expected 10million):

100.3814%
100.08197%
100.0936%
100.06955%
100.11825%
100.10609%
100.09413%
100.06938%
100.11526%
100.10894%
100.10597%
100.09374%
100.09683%
100.07576%
100.11881%
100.09578%
100.10504%
100.09339%
100.09367%
100.10843%
100.06451%
100.06077%
100.09165%
100.14474%
100.06321%
100.06088%
100.07508%
100.07083%
100.08172%
100.09126%
100.11141%
100.11209%
100.09601%
100.11616%
100.06668%
100.08558%
100.12031%
100.112%
100.08657%
100.11348%
100.12982%
100.1267%
100.11145%
100.0801%
100.11152%
100.09978%
100.11937%
100.10535%
100.08799%
100.06801%
100.09905%
100.09997%
100.07276%
100.12822%
100.12214%
100.0586%
100.10537%
100.10839%
100.08926%
100.11667%
100.0825%
100.12131%
100.03874%
100.05923%
100.14245%
100.09392%
100.09417%
99.8273%
99.7886%
99.80179%
99.78155%
99.82744%
99.77599%
99.76077%
99.81662%
99.77978%
99.82794%
99.8141%
99.82701%
99.78788%
99.77564%
99.80187%
99.80063%
99.7676%
99.80559%
99.78017%
99.8091%
99.81715%
99.78261%
99.81133%
99.79202%
99.76322%
99.77249%
99.76058%
99.77878%
99.84202%
99.80344%
99.81362%
99.78432%
99.79728%

ahhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh. Now the effect becomes nice and clear. (But is still tiny)

My questions are:

1. why did I have to do a BILLION (which is a huge number) times to see this nice and clear pattern?
2. why is the pattern so TINY
3. why does the switch from over the expected (were it an even distribution) to under the expected CLEARLY happen at 66? wouldn't 50 make more sense? It's a huge and clear shift and I bet it would repeat around there, given that the numbers above and below are clearly all in line and it's not like a statistical fluke (e.g. if 64 through 67, were just a hair away from each other and not actually in order but 66 "happened to" win out) , it follows the pattern decisively... I wonder why 66 (or two thirds of 99) is where it happens, it seems odd... why?

So: what are the mathematical reasons for such a tiny tiny slight favoring (like 0.1% it seems like over a billion iterations of the lower modulus numbers?), why don't they show up over a million iterations, and why does the shift from over the expected to under the expected number happen at 66 of 99 instead of something sensible like 50?

Thank you! 79.122.103.33 (talk) 17:43, 11 April 2009 (UTC)

I'm not quite sure I understand the problem. The remainders from 0 through 67 occur 328 times in the range, while the remainders from 68 through 99 only occur 327 times. So we would expect any low number (0–67) to occur with probability 328/32768 = 1.001% and any high number (68–99) with probability 327/32768 = 0.998%. It easily drowns in sheer randomness for too few trials. I have no idea why your result seems to treat 67 as a high number though. That seems weird. —JAO • T • C 18:03, 11 April 2009 (UTC)

Jao's answer is correct. For another explanation of why the shift happens where it does, think of a system where rand() returns numbers from 0-5 (like a die). Now, if you wanted a number between 0 and 4 exclusive, you could do rand() % 4, with the following possible outcomes:

• rand() returns 0 - result 0
• rand() returns 1 - result 1
• rand() returns 2 - result 2
• rand() returns 3 - result 3
• rand() returns 4 - result 0
• rand() returns 5 - result 1

It is easy to see that 0 or 1 would occur twice as often as the other numbers. If you made a similar table for 0-32767 and 0-99, you would see that the numbers 0-67 occur once more than the other numbers (namely, when the generator returns a number between 32000 and 32767). decltype (talk) 18:43, 11 April 2009 (UTC)

thanks for the answers! They make sense. So how would you correctly choose a number between 0 and 3 inclusive using a generator that goes from 0-5 inclusive, in an equally distributed way? Should you just reflip on a 4 or 5, no matter how many times you keep getting it? 79.122.103.33 (talk) 21:25, 11 April 2009 (UTC)

If you want an algorithm that's sure to stop, you can just flip it twice and see which ordered pair (like (1,1), (0,4) or (5,1)) you get. As there are 36 such ordered pairs, any scheme that maps nine of them to 0, nine to 1, nine to 2 and nine to 3 works. —JAO • T • C 22:12, 11 April 2009 (UTC)

To get uniformity at little cost, just reject values of rand() greater than 32699. Incidentally, it is usually recommended to use division rather than mod for this problem. That is, instead of rand() % 100, use rand() / 327 (after rejecting values above 32699). If rand() was perfectly random, it wouldn't make any difference, but division is considered less likely to magnify the imperfections of imperfect random number generators. McKay (talk) 01:45, 12 April 2009 (UTC)

okay then what is the answer

this is in relation to my thread two above (about weighted coins). so how many flips out of how many would I need to reach to be sure my coin isn't fair, for 75%, 90%, 95%, 98.5%, 99%, 99.9% confidence...

what is the formula? (this is not homework) 79.122.103.33 (talk) 21:21, 11 April 2009 (UTC)

The number of flips of the weighted coin that are necessary to ascertain which direction the weight is in (or to ascertain that it is weighted at all) to a specified level of confidence depends on the extent of the weight. At a fixed level of confidence, a coin with 2/3 probability of landing heads will be determined to be weighted much sooner than a coin with 501/1000 probability of landing heads. So the answer depends upon the amount of skew. Eric. 131.215.159.99 (talk) 23:32, 11 April 2009 (UTC)

how to do monte carlo properly

if after doing n flips and getting a certain number of heads, I want to be exactly 95% sure that the results show my coin favors heads (isnt fair) but I'm really bad at statistics, and want to do monte carlo instead, could I see what the most heads is in 20 runs (20 because 19/20th is 95%) by making a list of "most heads out of n flips in 20 runs" a billion times, average those numbers, and get my 95% threshold for n?

For example, if I want to see what number out of 50 flips my coin has to beat for me to be exactly 95% sure that it isn't fair, I average a billion metaruns of "most heads out of 50 flips, in 20 tries"?

sorry that I'm such a zero in statistics. this must be so frustrating to anyone who actually knows what's going on. anyway does this proposed methodology work for my intended confidence level (95%)?

if not this then what is the correct monte carlo method for the 95% interval? Thanks!79.122.103.33 (talk) 21:45, 11 April 2009 (UTC)

The distribution of the number of head in 20 tosses of a fair coin is approximately a normal distribution with a mean of 10 and a variance of 5, so a standard deviation of sqrt(5). In a normal distribution, 95% of observations are less than 1.65 standard deviations above the mean (since your question is "does my coin favour heads" then this is a one-sided test). 10 + 1.65 x sqrt(5) is approximately 13.7. So the probability that a coin that does not favour heads will score more than 13 heads in 20 tosses is less than 5%. So if your coin scores 14 or more heads, you can be "95% certain" that it favours heads. See hypothesis testing and Z-test for more details. Gandalf61 (talk) 12:25, 12 April 2009 (UTC)

You need to know the prior probability that the coin is biased before you can answer such a question precisely. See hypothesis testing (mentioned by Gandalf) for some discussion. Really, you've asked the question a couple very different ways: 1) you have a coin that is known to be biased, but you're not sure if it's towards heads or towards tails (let's say that's an implicit assumption that it's 50-50 guess between heads-biased or tails-biased); or 2) you have a coin that might be biased (with some unknown probability) and you want to check. Case 1 is straightforward: the null hypothesis is that the coin is biased towards tails, then compare the outcome of your experiment with the binomial or normal distribution. Case 2 is harder: for example, say you have 1000 coins, of which 999 are fair and one is 60-40 biased towards heads. You pick one of those coins uniformly at random, flip 20 times and get 14 heads. Are you 95% confident that you picked the biased coin? Nope, because of the prior probability distribution. In this case you'd use Bayes's theorem in conjunction with the known 0.999 prior probability to interpret the result. But if you don't know the prior probability, it's not so clear what to do. 66.127.52.118 (talk) 12:46, 12 April 2009 (UTC)

not knowing the prior probabiity, what can one do? If a magician lets you check a coin he's using, what are you supposed to guess for the chances it's fair? How woud you check? (to be 90% / 95% / 98% / 99% etc sure in your conclusion?) Thanks 94.27.222.70 (talk) 22:29, 12 April 2009 (UTC)

That is to some extent a question about philosophy rather than mathematics. See Bayesian probability and frequency probability (as well as statistical hypothesis testing already mentioned) for some discussion. 66.127.52.118 (talk) 01:19, 13 April 2009 (UTC)