Wikipedia:Reference desk/Archives/Mathematics/2014 November 20

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.

November 20

Proving the law of large numbers without defining probability

Is it possible to prove the law of large numbers without introducing the concept of probability?

This might seem like a strange question, so here's my motivation for asking it. In the frequentist interpretation of probability, the probability that an event $E$ occurs in an experiment is defined as $\lim _{N\rightarrow \infty }{\frac {N_{E}}{N}}$, where $N$ is the number of times the experiment is performed, and $N_{E}$ is the number of times event $E$ actually occurred in those experiments.

Obviously, this definition presumes that the above limit actually converges, a claim which isn't exactly non-trivial. It's usually stated as the law of large numbers, but the law of large numbers is typically proved only after the concept of probability has already been defined, making the whole thing a bit circular.

I happen to like the frequentist interpretation and would like to salvage it. This could be done if the law of large numbers could be proved without explicitly introducing ideas of probability. Does anyone know how this can be done? Thanks. 24.37.154.82 (talk) 00:09, 20 November 2014 (UTC)

I'd think the law of large numbers is mostly an empirical thing. — Melab±1 ☎ 03:46, 20 November 2014 (UTC)

No, it isn't. Our article law of large numbers has a bad intro IMO. We can use the LLN as a result of a model of something, and then apply it to some experiment, but the statement and proof of the theorem are just regular pure mathematics. SemanticMantis (talk) 16:29, 20 November 2014 (UTC)

It isn't circular, and you can define probabilities without resorting to the limit you describe (Which does have sort of an empirical feel, and that might explain Melab's comment). For example, I can define the probability of getting heads (H) or tails (T) on a fair coin toss (x) without using any limit statements or invoking LLN: $\mathbb {P} (x=H)=1/2,\mathbb {P} (x=T)=1/2$ -- see? Maybe you were confused because we can invoke the LLN as a means of justifying a method to estimate a probability when only empirical experiments are available. There's nothing wrong with the frequentist interpretation either. Or rather, it has some problems, but all such interpretations do. The Bayesian approach also has problems, and rather than there being some huge distinction in world views or philosophy of math, people tend to just use whichever framework is most suitable for the problem at hand. SemanticMantis (talk) 16:29, 20 November 2014 (UTC)

Sure, you can define the probability that a fair coin lands on heads as ${\frac {1}{2}}$, but this definition carries zero content. You might as well define the $\mathbb {P} (x=H)={\frac {1}{e}}$. The fact that we favour one value over another for the probability of a fair coin landing on heads tells us that it is more than a mere definition. 24.37.154.82 (talk) 17:01, 20 November 2014 (UTC)

Of course it's just a definition, made up to conform with our notion of "fair". How can you say it has zero content? It fully specifies the probability of the events occurring. Of course, some weighted coin might indeed have 1/e chance of ending up heads, and it's your prerogative if you want to define a certain mathematical probability in that manner. Backing away from this issue: the LLN is a theorem about probability theory, and as such, it depends on axioms of probability. There's really no way around that, and it doesn't entail any specific problem with the frequentist interpretation. You might want to read up on other Probability_interpretations, but all of them have the LLN depending on the same axioms and definitions that compose the classical discrete probability. SemanticMantis (talk) 20:42, 20 November 2014 (UTC)

I should further clarify: the different interpretations of probability have to do with how we make inferences about the real world based on mathematical constructs. None of the interpretations change the mathematics of probability. From a mathematics perspective, all probability theory can be constructed axiomatically, and has no technical need for any outside interpretation. SemanticMantis (talk) 20:46, 20 November 2014 (UTC)

We're talking over each other.

Until you define what you mean by "probability", you can't present an argument for why a fair coin should have probability of $1/2$ to land on heads. If you try to avoid a discussion of what probability actually is by just defining the probability that a coin lands on heads as $1/2$ -- which is what I thought you were doing above -- I would reply that the definition carries zero content. 76.68.233.159 (talk) 01:30, 21 November 2014 (UTC)

If you're still reading, I apologize for the confusion. You're right, I defined a specific probability without really defining what a probability really is. There is a bit of a break between the machinery necessary to define the probability associated with discrete outcomes and finite numbers of experiments, compared to the way we define probabilities for the continuous case or for an infinite number of coin tosses. The former can be done relatively simply, but the latter is somewhat difficult. See probability axioms for the latter case. Rigorously defining "probability" in a general and axiomatic way is rather recent, and was only completed by Kolmogorov. Prior to that, people had been a little fast and loose with the foundations, and perhaps that is what you are picking up on. But to do all this rigorously means some time has to be spent constructing measure theory, and few people outside a graduate program in math will go that far. Anyway, the treatment of defining probability axiomatically as described in our article doesn't depend on any notion of LLN or the limit statements you have at the top. It is not circular, though it may often be presented in a semi-circular fashion if the students and instructor don't have the time and background to go through Lebesgue measure and all that. Does that help answer your question? SemanticMantis (talk) 14:37, 21 November 2014 (UTC)

See Principle of indifference why the probability for heads and tails should be equal. Bo Jacoby (talk) 22:48, 20 November 2014 (UTC).

${\frac {N_{E}}{N}}$ is the probability that a randomly chosen one among the $N$ experiments was $E$.

${\frac {1+N_{E}}{2+N}}$ is the probability that the next experiment will be $E$.

Bo Jacoby (talk) 09:28, 21 November 2014 (UTC).

I'm surprised that nobody brought up sums of binomial coefficients yet.

Let n be an even integer. Then, let S_n be the sum of the 2n+1 coefficients (^n²_n²/2–n) to (^n²_n²/2+n). For large n, S_n / 2^n² (the denominator being the sum of all BCs with upper index n²) approach a non-zero value, even though they represent a diminishing fraction of the BCs with upper index n².

Now, the law of large numbers says something else, namely that the sum of a fixed fraction of BCs should approach unity. However, if we look at other sums, for example, the sum of the 2kn+1 coefficients (^n²_n²/2–kn) to (^n²_n²/2+kn), for increasing k, we find that these approach fractions closer and closer to unity with increasing k. This should result in the LoLN for the case p=1/2.

I hope that's accessible to the OP. 217.255.188.220 (talk) 07:12, 26 November 2014 (UTC)

edit on https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Interpolation_on_the_unit_interval_without_exact_derivatives

I changed 1/2 ( x vector dot p vector) for Cint equation to - 1/2 ( x vector dot p vector ). I'm pretty sure this is correct by experiment but hope I could get someone to confirm the edit is correct.

PLEASE disregard. +1/2 is correct. Satisfied by using 1/2 in corrected experiment.

I guess I'll mark this

Resolved

, also please remember to sign posts with four tildes, like this: ~~~~ SemanticMantis (talk) 16:15, 20 November 2014 (UTC)

Integration by parts

Why is it sometimes necessary to integrate twice using integration by parts? For example, when calculating the response to a unit step function in vibration theory, duhanel integral is used. In many of these cases integration by parts is used twice but what is the mathematical reasoning behind this? 217.33.132.194 (talk) 19:27, 20 November 2014 (UTC)

I put this question in a new section, which will happen automatically if you use the button at the top of the page. Have you read our article on integration by parts? If you can follow it, it gives a proof of why that formula is the correct formula. It just depends on the product rule and the fundamental theorem of calculus. It's just sort of the inverse of the product rule. If you don't understand the proof, tell us where you are stuck and we might be able to help further. SemanticMantis (talk)

Minimum angle between edges of a circle in a grid

I completely messed up this question a few days ago. I was going to reply back in the mess I made, but thought it better to give this a fresh start and state my solution - in case it is easier to make it better...

This problem takes place in a grid. It is pixels on a computer screen. Each is a square. The coordinate 0,0 is the center of the grid. It is the center of the pixel in the center of the grid. That is important to note. 0,0 is not the corner shared by four pixels. It is the center pixel itself. 0,1 is the pixel directly above 0,0. 1,0 is the pixel directly to the right of 0,0.

The goal is find the maximum angle increment that if I make a circle beginning at 0,r (for an integer radius r) and consider that an angle of 0 radians, I will step around the circle, in increments of the angle increment, filling in the pixel that is touched by the edge of the circle. The algorithm for drawing the circle is:

• Let a=0 (angle in radians - this is where I messed up before. I called the angle r)
• Let i be the increment
• Draw a line from 0,0 that is r units long (a unit is the width of a pixel) at an angle a where 0 radians is straight up to 0,r, 0.5PI is at r,0, PI is at 0,-r, 0.75PI is at -r,0, and 2PI is back to 0,r.
  • I hope I got that right. A circle is 2PI radians, right?
• Increment a by i and go back to the previous step until a>=2PI

My solution is very much a cheat. I create an image that is r by r pixels. I draw a quarter arc on it using the graphics libraries in the computer program. I then create another image that is r by r pixels. I draw a single dot at 0,r, increment a, draw the next dot wherever that angle places the line, increment a again, and draw. I keep incrementing until a>0.5PI. Then, I compare the image I drew to the original one. If I missed a pixel, the increment needs to be smaller.

One suggestion was that the increment must be the angle between the 0,r and 1,r from 0,0. I don't think that is actually the maximum i that still allows every pixel around the edge of the circle to be touched. 209.149.113.112 (talk) 21:07, 20 November 2014 (UTC)

Borrowed from Bresenham's circle algorithm to help clarify the question.

Are these old contest problems available for us to view online? I ask because the precise statement of the problem is still not clear to me, and I was hoping to see the official wording. -- ToE 21:51, 20 November 2014 (UTC)

Or perhaps you can clarify it directly by saying if the pixels shaded in the image to the right are sufficient, even though there are several which do intersect the circle (their corners are clipped) but are not shaded? -- ToE 22:52, 20 November 2014 (UTC)

They are old contest problems (from the ACM programming competition). This is one that I technically got correct, but I didn't like my solution. I haven't been able to find it online which is why I'm planning to use it for the upcoming end-of-semester competition. I didn't realize the sublety of this that you noted. The problem (from memory) stated that a complete circle must be drawn such that there is no gap. So, your image meets the requirement even though there are pixels touched by the circle's outline that are not shaded. That will increase the complication of writing the problem. If you don't mind, I will be stealing that image. 75.139.70.50 (talk) 00:51, 21 November 2014 (UTC)

The standard solution to this problem is to use the property that for a circle, $x^{2}+y^{2}=r^{2}$. You can solve this for y and use it to draw 1/8th of a circle, from the top down to 45 degrees from the top. The other 7 parts can be generated by mirroring twice (so you get two quarter circles, one on top, one on the bottom) and then exchanging the axes for the remaining two quarters left and right. If you do it that way, your angle of the circle will never be more than 45 degrees, so you will never miss a pixel on the y axis when you step along the x axis. --Stephan Schulz (talk) 01:06, 21 November 2014 (UTC)

If you needed every pixed which intersects the circle in the slightest to be shaded, then I suspect that not only will there not be a simple formula for i in terms of r, but there won't even be a simple formula for a positive lower bound for i based on r. For some r, the circle will just happen to clip one pixel so close to the edge that i will have to be very small in order to touch that pixel and its 7 mirror images, but for r one larger or one smaller a much larger i would be suitable. Perhaps someone here can speak to the mathematics behind this pseudorandom(?) behavior.

But if the goal is simply no gap, and this is satisfied by corner touching, then it is much easier. Note that any two points which are at most 1 unit apart are either in the same pixel or on neighboring pixels (an 8-neighbor that is, sharing either sides or corners). So, what increment i yields points which are at most 1 unit apart on the circle? An easy answer is to let i = 1/r, because the distance along a the arc of a circle of radius r separated by θ radians is rθ. So two points on your circle separated by i radians are r⋅i = r(1/r) = 1 unit apart along the arc. We are interested in straight line distances, so we can tighten it up a bit by measuring along the chord. Do the trig and you will find that an increment of i = 2 arcsin(1/(2r)) = 2 arccsc(2r) will give you points exactly 1 unit apart. Either considering this geometrically or looking at the infinite series expansion for arccsc, it is clear that for large r, 2 arccsc(2r) ≈ 1/r, approaching 1/r from above (so it is a slight better, as in larger, increment, but not by much).

I suspect that, in practice, this will be the best, simple answer. In theory, a slightly larger i should work for most r, because the pixels present their smallest diameter when viewed from the origin) along the axes, and you are already starting in the middle of the pixel there, so you could afford a slightly larger increment and still catch neighboring pixels as you worked along the first 45°. But your algorithm does not stop there and mirror the results. It instead continues around the full circle, passing in the vicinity of the axes several more time, risking skipping a pixel along the way. Still, if you solved this numerically for each r, you should find values for i slightly larger than 2 arccsc(2r), but that, or simply 1/r, offer a good lower bound for i.

Your solution was ingenious, but it does have some problems. Look at the diagram and note the pixel with the dot at 45°. If the pixel below it was shaded, instead of the one below and to the right, that would still be a valid pixelated circle. So there are some value of i which will give a valid result, but will fail your test because it won't match the circle drawn by you graphics library. Back to the diagram, if the pixel below the 45° dotted pixel was shaded in addition to the one below and to the right, then that is still a valid pixelated circle, just not a minimal one. Once you get your i small enough, you will be picking up additional pixels not needed by the 8-neighbor no-gap rule. If you are testing your result against that drawn by the graphics library for equality, this could be a problem as your algorithm may never find a solution for some r, but if you are just testing that you didn't miss any of their pixels (as you stated), then that should be OK. Finally, it is possible that you might happen upon an i for some r which is slightly larger than 2 arccsc(2r), and which works for the first 45°, but fails at some point in the following 315°. -- ToE 11:50, 21 November 2014 (UTC) I □ pixels.

If each pixel has 8 neighbors (N NE E SE S SW W NW), then a king can follow a curve of pixels. Such a set of pixels may be called a king-curve. If each pixel has 4 neighbors (N E S W), then a rook can follow a curve of pixels. Such a set of pixels may be called a rook-curve. King-curves without common pixels may cross one another, but a king-curve and a rook-curve without common pixels do not cross. You may define that each pixel has 6 neighbors (N NE SE S SW NW) like in chinese checkers. Chinese-checkers-curves without common pixels do not cross. The coordinates to the pixels may be

(x , y) = (3 i , √3 j)

where i and j are integers and where i+j is even. Bo Jacoby (talk) 19:38, 21 November 2014 (UTC).