Wikipedia:Reference desk/Archives/Mathematics/2015 September 29

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.

September 29

Difference tends to 0

Two functions on the natural numbers are asymptotically equivalent if their quotient tends to 1. Is there a similar term for pairs of functions whose difference tends to 0? GeoffreyT2000 (talk) 02:55, 29 September 2015 (UTC)

I don't know of a name, but it is perhaps worth noting that if the difference converges to 0 and each function is bounded away from zero in the asymptote then this already implies that the quotient tends to 1, and hence that the functions are asymptotically equivalent. So the ideas are quite similar, and perhaps there isn't a new name. I would also note that the converse is not true. Quotient tends to 1 does not generally imply a difference goes to zero (e.g. lim (x+5)/x as x increases). Dragons flight (talk) 07:49, 29 September 2015 (UTC)

If the difference tends to zero, then the functions are curvilinear asymptotic (as well as asymptotically equivalent). Dbfirs 08:19, 29 September 2015 (UTC)

I think for something like this you could use something like f(n) = g(n) + o(1); see the little o section of Big O notation. --RDBury (talk) 15:59, 29 September 2015 (UTC)

Law of large numbers and the running average

So according to the law of large numbers, the sample mean for a well behaved variable will approach the true mean following sufficiently many observations. I'm curious though about how the sample mean changes as you increase the number of observations. So consider an experiment that repeats for infinitely many trials. The running sample mean is the average of all measures of variable X on trials 1 to N. According to the LLN, the running sample mean should trend toward the true mean as N increases. But if we allow N to increase forever, does it have a chance of deviating from the true mean even momentarily?

I hope I'm getting my question across properly. Obviously, if I decide to only look at the last K trials, I will inevitably get a group of K trials that deviates significantly from the true mean. It's simple to ask a question like, for a series of N coin tosses, what is the chance that more than 51% of tosses results in heads? Easy. But what about this question, the same as my original but formulated differently: Bob begins tossing a coin. He never ever stops. Assuming he tosses his coin at least K times, what is the chance that he ever sees more than 51% of his total tosses result in heads?

My question is partially motivated by a putative method of data rigging in scientific experiments - if you don't get the results you want, repeat the test. Include all data in your average, but just keep going until the average is what you want. I'm wondering if this is even a feasible thing to do, statistically. Someguy1221 (talk) 03:44, 29 September 2015 (UTC)

Yes, there is a non-zero chance that any possible deviation occurs in the sequence of partial means. For example, there is roughly a 6.2% chance that a fair coin has produced 60% heads at some point after 10 trials. Such odds diminish with the number of trials. For example, after 20 or more trials, the odds of encountering 60% heads of a fair coin drops to about 0.7%. The larger the deviation from the true mean, the less likely it is be encountered by continued random testing. Dragons flight (talk) 08:00, 29 September 2015 (UTC)

Could you let me know how you calculate that? Might help me understand how to prove the probability is greater than 0 but not 1. Thanks. Someguy1221 (talk) 08:23, 29 September 2015 (UTC)

This doesn't seem right. The probability of >=60% heads at the 11th trial is 27.4%. The probability it will be >=60% at some point from 11th trial and up should be higher (and if you meant 10th and up, higher still - I got in simulation 52% for that). -- Meni Rosenfeld (talk) 18:52, 29 September 2015 (UTC)

See large deviations theory, and especially the first example where the probability that the sample mean after N trials deviates from the mean of the random variable is determined. Sławomir
Biały 10:18, 29 September 2015 (UTC)

It is useful to introduce some notation. For the coin case, let $X_{i}$ be iid Bernoulli trials with probability 1/2. Let $Y_{i}=\sum _{j=1}^{i}X_{i}$ and $Z_{i}=Y_{i}/i$. You are asking, for some k, what is the probability that there is $i\geq k$ such that $Z_{i}\geq 0.51$?

It is easier to calculate the expectation of the number of $i\geq k$ such that $Z_{i}\geq 0.51$. This is equal to $\mathbb {E} [\sum _{i=k}^{\infty }[Z_{i}\geq 0.51]=\sum _{i=k}^{\infty }\mathbb {E} [[Z_{i}\geq 0.51]]=\sum _{i=k}^{\infty }\mathrm {Pr} (Z_{i}\geq 0.51)$. The variables $Z_{i}$ are not independent but that does not stop us from using the linearity of expectation. You can estimate each summand based on the binomial distribution or normal approximation. For large enough k, you'll find that the result is between 0 and 1, from which it follows that the chance there will be at least one such i is also between 0 and 1. (Note that because of the large correlations, the actual probability will be much less than this calculated mean). -- Meni Rosenfeld (talk) 13:22, 29 September 2015 (UTC)

(ec) That is a good question, and the answer is not immediately obvious. The answer is 1. It is almost certain that it eventually happens that more than 51% of the total tosses result in heads.

The probability that it ever happens is the complement of the probability that it never happens.

The probability that is never happens is the product of the probabilities that it does not happen.

The probability that it does not happen is the complement of the probability that it does happen.

The event of crossing the 51% line from below means that i/n ≤ 0.51 and (i+1)/(n+1) > 0.51. So 0.51n−0.49 < i ≤ 0.51n. If integer i is less or equal to x, then i is also less or equal to the floor function of x. So 0.51n−0.49 < i = floor(0.51n). The crossing can happen only when 0.51n−0.49 < floor(0.51n), and the corresponding i-value is i = floor(0.51n). The probability for that is

${\binom {n}{i}}2^{-n}$

and the probability that the toss number n+1 is head is 1/2.

So the probability of a crossing after n is

$p_{n}=\left[0.51n-0.49<floor(0.51n)\right]{\frac {1}{2}}{\binom {n}{floor(0.51n)}}2^{-n}$

The probability of no crossing at n is

$1-p_{n}$

The probability of crossing never is

$\prod _{n=k}^{\infty }(1-p_{n})$

and the probability of crossing ever is

$1-\prod _{n=k}^{\infty }(1-p_{n})$

This expression is coded in J. Starting at K=100, tossing 900 times more. The probability of ever crossing the 51% line is

1-*/1-(m<i+0.49)*(n!~i=.<.m=.0.51*n)%2^1+n=.100+i.900

0.999617

Bo Jacoby (talk) 14:46, 29 September 2015 (UTC).

I'm sorry but that's obviously false. Your statement directly contradicts the LLN. If it's almost sure to happen no matter where we start, then it's almost sure to happen infinitely many times, and the sample means can't converge.

Your main problem is that you've chosen k too small. At 100 tosses, the number of heads has mean 50 and sd 5, so naturally there is a high chance of getting more than 51%. So the result was close enough to 1 that you were tricked into thinking the difference is merely due to not summing all the way.

Try a bigger k (say 100,000. Alternatively, a bigger value than 51%) and you'll see how the probability is not 1. If you think about it, you are in fact suggesting that the last expression is 1 no matter what k is, which is impossible since adding terms in the beginning obviously changes the result (unless all the p's are zero, which they're not).

Your other problem is that you've incorrectly assumed the events are independent. You can't multiply out the probabilities like this. I'm not sure if this materially affects the result. -- Meni Rosenfeld (talk) 16:05, 29 September 2015 (UTC)

Hello Meni! You are probably right. Feel free to improve my result.

1. The LLN does not say that the mean always converges. I says that the mean almost always converges. Infinite sequences of 0s and 1s having divergent means are improbable but not impossible.
2. Any finite value of k is dwarfed by the infinity. Is it obvious that the probability depends on k?
3. My program does not allow k=10000 as 2^1024 evaluates to infinity.
4. Rather than computing the probability one could simulate. Computing the maximum mean of 50000 random coin tosses, omitting the first 1000:

2^1023 1024

8.98847e307 _

p=. 4 :'1-*/1-(m<i+1-x)*(y!~i=.<.m=.x*y)%2^1+y'

0.51 p 300+i.730

0.994277

0.55 p 300+i.730

0.321506

E=.+/%#

>./1000}.E\?50000#2

0.513206

>./1000}.E\?50000#2

0.509849

>./1000}.E\?50000#2

0.513487

Bo Jacoby (talk) 22:25, 29 September 2015 (UTC).

1. Right, that's why I specified it's not just able to diverge, it almost surely diverges. The LLN says it converges with probability 1, and a result of your statement is that it converges with probability 0. So the statements aren't compatible.
2. Actually what I said about the dependence of k is incorrect, just from the expression it's not obvious it can't be 1. The real reason it's obvious is the nature of Brownian motion. Progress of Brownian motion is square-root in nature, and here we expect it to catch up with a linearly growing target. If it doesn't catch up in the beginning, there's a good chance it will never catch up (with the probability of catching up decreasing exponentially, and thus the sum converging to a small amount). You might be interested in my analysis of an equivalent problem (bankruptcy of PPS Bitcoin mining pools) here, appendix C.
3. Well, consider switching to Mathematica :). I implemented this in Mathematica (I made some continuity approximations) and got a result of 0.672 for k=10,000, and 6.21E-9 for k=100,000. This is assuming your expression is correct, about which I'm not sure because of the independence issue. Alternatively, you can also see this by keeping k low and increasing the threshold to, say 75%.
4. It seems the simulation corroborates that 51% is fairly easy to reach at the ~1000 tosses range, but larger deviations will be difficult - and of course, with larger k, 51% won't be reached either.

-- Meni Rosenfeld (talk) 09:13, 30 September 2015 (UTC)

Thanks. Considering switching, please show what the J program looks like when converted to Mathematica. A continuity approximation is convenient because the exact formula gives huge intermediate result.

${\binom {n}{i}}2^{-n}\approx {\frac {e^{-{\frac {z^{2}}{2}}}}{\sqrt {2\pi }}}dz$ where $z={\frac {i-\mu }{\sigma }}$ and $\mu ={\frac {n}{2}}$ and $\sigma ={\frac {\sqrt {n}}{2}}$ and $dz={\frac {di}{\sigma }}$ and $di=1$

In J this is:

q =. 4 : '(^--:*:s%~x--:y)%(%:o.2)*s=.-:%:y'

Using this approximation the probability computation is

p =. 4 : '-.*/-.(m<i+1-x)*-:(i=.<.m=.x*y) q y'

The test computation

0.51 p 300+i.730

0.99446

is reasonably close to the former result 0.994277.

Meni Rosenfeld's example k=10000

0.51 p 10000+i.100000

0.675687

is reasonably close to Meni's result of 0.672

Bo Jacoby (talk) 18:16, 3 October 2015 (UTC).

This is the Mathematica code I used:

q[n_] := 0.49*1/2*Binomial[n, 0.51 n] 2^-n
1 - Exp[NSum[Log[1 - q[n]], {n, 10000, \[Infinity]}]]

The continuity approximation is in replacing $[0.51n-0.49<\lfloor 0.51n\rfloor ]$ with 0.49, and ${\binom {n}{\lfloor 0.51n\rfloor }}$ with ${\binom {n}{0.51n}}$ (with the Gamma function used for the extension). This makes it tremendously easier to use numerical summation methods.

If I were to use the original form without any optimizations, it would look something like

q[n_] := If[0.51 n - 0.49 < Floor[0.51 n], 1, 0]*1/2*Binomial[n, Floor[0.51 n]] 2^-n
1 - Exp[Sum[Log[1 - q[n]], {n, 10000, \[Infinity]}]]

-- Meni Rosenfeld (talk) 20:09, 3 October 2015 (UTC)

Thanks! I am amazed that those approximations optimized the Mathematica computation.

p1=. 4 : '-.*/-.(m<i+-.x)*(y!~i=.<.m=.x*y)*2^-1+y' NB. using binom dist

p2=. 4 : '-.*/-.(m<i+-.x)*-:(i=.<.m=.x*y) q y' NB. using normal dist

p3=. 4 : '-.*/-.(-.x)*-:(x*y) q y' NB. including Meni's approximation too

e1=. 300+i.730 NB. example k=300

(0.51 p1 e1) = 0.994451

(0.51 p2 e1) = 0.99446

(0.51 p3 e1) = 0.994021

The p2 program is preciser than the p3 program.

e2=. 1e4+i.7e4 NB. example k=10000

NB. (0.51 p1 e2) gives NAN error after a long time

(0.51 p2 e2) = 0.675687

(0.51 p3 e2) = 0.672072

Bo Jacoby (talk) 04:43, 4 October 2015 (UTC).

Answering the OP's question. After tossing a coin K times, what is the probability of ever getting more than 51% heads?

  6 7j4":K,.0.51 p2 (i.7e4)+/K=.1000*1+i.25
 1000 1.0000
 2000 0.9999
 3000 0.9989
 4000 0.9939
 5000 0.9796
 6000 0.9504
 7000 0.9030
 8000 0.8384
 9000 0.7607
10000 0.6757
11000 0.5891
12000 0.5055
13000 0.4282
14000 0.3588
15000 0.2981
16000 0.2460
17000 0.2019
18000 0.1651
19000 0.1345
20000 0.1093
21000 0.0887
22000 0.0718
23000 0.0581
24000 0.0470
25000 0.0380

Bo Jacoby (talk) 11:31, 4 October 2015 (UTC).

The above results are interpolated by this expression:

$1-e^{-e^{2.6-0.00024K}}$

This is the requested solution. Bo Jacoby (talk) 18:00, 4 October 2015 (UTC).

Primitive part of fibonacci

The last section of the article fibonacci prime has a red link to something called the "primitive part" which doesn't seem to be defined anywhere. It appears that what's intended is the product of prime factors of F_n of which are not factors of previous entries. It looks like the corresponding OEIS sequence calls these primitive primes, though it's not really defined. [1] defines primitive part somewhat differently, and I get the primitive part of F₆ as 4 according to it, not 1 as listed in the article. This definition gives OEIS: A061446 which OEIS also calls primitive part. There are other definitions floating around though, e.g. something called the Lucas-Aurifeuillian primitive part. Is there a standard definition of primitive part being used in the article or is it the result of confusing primitive part and primitive prime? --RDBury (talk) 17:11, 29 September 2015 (UTC)

To be honest I would support simply cutting the material if there is no other reference than an ambiguous OEIS reference. --JBL (talk) 22:53, 4 October 2015 (UTC)

Thanks; I probably won't cut it but some free and merciless editing will probably help. There may be a notable concept in primitive part, just not the one used in the article. --RDBury (talk) 17:25, 5 October 2015 (UTC)