Mathematics desk
< November 28	<< Oct \| November \| Dec >>	November 30 >

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 29

n choose k with replacement

The expected value for the number of unique elements in a sample of size k which is chosen with replacement from a population of n object is $n\cdot \left(1-\left(1-{\frac {1}{n}}\right)^{k}\right)$ . If r = k / n, then the expected fraction of the total population represented by the unique elements of the sample is $1-\left(1-{\frac {1}{n}}\right)^{r\cdot n}$ . As n→∞, this fraction goes to 1 - e^-r, yielding the famous result that the fraction of unique elements picked with replacement in a sample size equal to the population size goes to 1-1/e as n→∞.

Is all this discussed in any Wikipedia article? I thought that it and related concepts (such as the distribution for samples with various numbers of unique elements -- is that what Stirling numbers of the second kind deal with?) might be found if only I could figure out the proper article title. I've found nothing relevant in the see also sections of Hypergeometric distribution, Coupon collector's problem, & Birthday problem. Perhaps the subject is insufficiently notable to merit an article. (Or even more likely, perhaps it's in one of the articles I linked, but I'm just too blind to pick it out.) -- ToE 18:09, 29 November 2014 (UTC)[reply]

Determinant

I've posted on this issue before and got the answer I needed and now I have to ask some additional questions. Before I began I need to say that it is a computational work and I need to write a program that will do it all for me. I have a 2-sphere with two points $\mathbf {X_{1}}$ and $\mathbf {X_{2}}$ defined on it. I know their spherical and Cartesian coordinates. $\mathbf {X_{1}}$ and $\mathbf {X_{2}}$ are of course vectors drawn from the center of the sphere to those points on the sphere. One can draw a plane ${\mathfrak {P}}$ through these two vectors. I now have a third vector $\mathbf {X_{3}}$ which is located somewhere on 2-sphere. The program knows it's coordinates. What my program needs to do is to move the third vector toward the plane, perhaps in an optimal way, I don't know how to define it, in such a manner that the third vector will eventually lie on the plane ${\mathfrak {P}}$ . I know how to do it. I will increment/decrement angles φ or θ or both and compute the determinant of the matrix composed of the Cartesian coordinates of all three vectors and try to catch the moment when it becomes computationally zero. But I need this third vector to lie between the two initial vectors, not outside of them. Not only that. I will have to eventually cover the distance (on the sphere) between two initial vectors $\mathbf {X_{1}}$ and $\mathbf {X_{2}}$ with a multitude of points which are zeroes of some orthogonal polynomials, so I have to judge the positions on this arc of the great circle well.

There is a chance that in some cases the program will choose the wrong direction and will go around through 2 $\pi$ angle and waste computer time. I would like to have criteria that will help me to do it optimally. The moment when the third, moving vector $\mathbf {X_{3}}$ crosses the plane ${\mathfrak {P}}$ I can probably detect two ways: the sign of determinant should change and its magnitude will begin to grow again, correct?

I also want to know how I can compute orbital (angular) distance between two arbitrary vectors on the sphere.

The most important question for me now is how to optimize the walk of the third vector across the sphere. Thanks, --AboutFace 22 (talk) 18:45, 29 November 2014 (UTC)[reply]

The distance between ttwo points of the unit sphere is given by the inverse cosine of their dot product. To optimize the path of the third point, use polar coordinates in the plane containing x3 and the cross product of x1 with x2. Sławomir Biały (talk) 19:57, 29 November 2014 (UTC)[reply]

Can you help clarify what you want to do by explaining a concrete example? For instance, using latitude and longitude, let X₁ = (0°,0°) -- the intersection of equator and prime meridian -- and X₂ = (0°,10°W). The two points determine a plane, in this case the equatorial plane. If X₃ = (45°N,5°W), then its projection onto the equatorial plane and extension out to the equator puts you between X₁ and X₂, so presumably you want the path down the 10°W meridian from 45°N to the equator. But what for X₃ such as (45°N,175°W), whose projection onto the equator does not lie between X₁ and X₂? Are you now seeking a great circle arc from X₃ to the closest point on the equator between X₁ and X₂? (I suppose that for many choices of X₃, the closets point on that arc will be an end point.) -- ToE 20:14, 29 November 2014 (UTC)[reply]

Finding the end points of the vectors is trivial, they are given. I will try to explain my task more carefully. I may have a rectangle on the sphere located anywhere you can imagine. The only limitation is it all will be in the North hemisphere. The rectangle may be rather small. The sides of the rectangles will not necessarily be oriented along meridians or parallels but each side of the rectangle will be a part of some Great circle. In some cases this rectangle may be initially defined around the North Pole and then moved away with three Euler's angles but it is just a particular case. There will be a function F(θ,φ) defined on this rectangle ONLY. On the rest of the sphere F(θ,φ) == 0. I want to do integration on this rectangle with the purpose to compute two-D transforms eventually and I don't want to waste time and resources to do it over all the sphere. I hope to find boundaries of the rectangle, populate it in one direction (meridional) with points which are zeroes of Legendre or Chebyshev polynomials, do integration and do a FFT in the latitudinal direction.

The way I initially imagined this task was that I will have to do a "random walk" and when my program carrying vector $\mathbf {X_{3}}$ will stumble on one of the rectangle boundaries I will register that. As the first poster, Sławomir Biały, pointed out there might be a better way. I will look into it. Thanks, --AboutFace 22 (talk) 01:49, 30 November 2014 (UTC)[reply]

An obvious way to bring your third point onto the given plane is to use the vector rejection and then normalize. — What do you mean by "rectangle"? A right-angled quadrilateral whose boundaries are all great circles must have zero area. —Tamfang (talk) 03:52, 30 November 2014 (UTC)[reply]

I projected a rectangle, or rather a combination of rectangles constituting a letter H (three rectangles) onto 2-Sphere. I also projected many points between the corners of the rectangles and computed determinants of three vectors, two pointing to the corners and one lying in between. They all were computationally zeroes and I assumed that they all lied on great circle(s). I am not sure if the corners of the rectangles have right angles, and it is the least of my concerns. I know what they are. I simply have four points for each rectangle on 2-sphere and must go from there. The algorithm calls for finding all points pertaining the sides of the rectangles on 2-sphere when only four corner points are defined. Thanks, --AboutFace 22 (talk) 16:13, 30 November 2014 (UTC)[reply]

Tamfang, thank you. It looks like this is what I need: vector rejection. I may have some additional questions but not now. --AboutFace 22 (talk) 16:26, 30 November 2014 (UTC)[reply]

In the end I am still struggling. I tried to use the Sławomir Biały's suggestion: to use polar coordinates in the plane containing

\mathbf {X_{3}}

and the cross product

\mathbf {X_{1}} \otimes \mathbf {X_{2}}

. The cross product is easily computed but what to do next I don't know. Likewise Tamfang's suggestion to use the vector rejection is also unclear how to use. In any case it seems the only option is to walk over the sphere and compute angles and distances. I also need to determine if my

\mathbf {X_{3}}

is inside a rectangle in question or outside of it. I tried to use Flag Theorem but it is non-specific. It gives the same result even if the vector

\mathbf {X_{3}}

is outside of the figure. I need some additional help here. Thanks, --AboutFace 22 (talk) 23:45, 30 November 2014 (UTC)[reply]

Perhaps you can frame better what you are trying to achieve. Part of your description sounds like you would like a parametrization of a curve on the sphere. Taking your X₁ and X₂, it is easy enough to find the great circle through them. Then given X₃, you can find a great circle arc from it to the previous great circle: say the shortest arc, the one through X₁, or the one through X₂. One can then find a simple trigonometric formula that maps 0 to X₃, 1 to the chosen point on the first great circle, and the interval in between uniformly onto the arc. Is this what you want? —Quondum 02:28, 1 December 2014 (UTC)[reply]

Quondum, thank you. It is all about integration. Naturally I try to break the task into small pieces and this is one of them. Given two unit vectors with known spherical coordinates $\mathbf {X_{1}}$ and $\mathbf {X_{2}}$ I need to place the third vector $\mathbf {X_{3}}$ in the same plane (a great circle) in between the first two vectors at once! I can do it by, let say, doing Monte Carlo and computing the determinant composed of coordinates of the three vectors and catch the moment when it becomes zero. This is the only method I clearly see now. There are some other sketches of ideas but none of them is optimal now. Could you elaborate what you are suggesting? In the meantime I will keep thinking about it. Also it occured to me that I can define at least one coordinate of the vector $\mathbf {X_{3}}$ and that is angle φ, so it may be given. Now I will have to find the other one: θ. --AboutFace 22 (talk) 14:52, 1 December 2014 (UTC)[reply]

If you are simply trying to find any point on the great circle defined as that containing both X₁ and X₂, it is simple to find a mapping from [0,2π) to all these points. You don't need to search to get a zero determinant (the dot product with the pole to the great circle would be equivalent): this mapping will produce exactly every unit vector for which the determinant is zero. Since you are talking about integration, let's assume you wanted to integrate something along the arc I mentioned before. You'd integrate for the path parameter between 0 and 1; no need to calculate any other condition (such as your determinant). —Quondum 15:19, 1 December 2014 (UTC)[reply]

Well, I need to populate the stretch of the great circle between the two vectors $\mathbf {X_{1}}$ and $\mathbf {X_{2}}$ with zeroes of some orthogonal polynomials and they are not evenly distributed. In this sense it is not any point but I will read your post carefully and think about it. Thank you, --AboutFace 22 (talk) 15:37, 1 December 2014 (UTC)[reply]

If I am reading between the lines correctly, your polynomials are defined over an interval on the real line, which I suppose is to be mapped uniformly to the great circle arc between X₁ and X₂. Knowing where the zeros are on the real line will allow a direct mapping of each zero onto a point on the arc. —Quondum 21:43, 1 December 2014 (UTC)[reply]

You don't have to read between the lines :-) It is Gauss-Legendre or Gauss-Chebyshev integration in direction of longitude (meridian). Of course it is on a real line. It is between 20 and 100 points depending on accuracy required. The actual number is something that remains to be determined. The problem is: I want to optimize the process and make sure the integration is confined to only a certain figure, in the simplest case, a rectangle. I don't want to integrate over all 2-sphere like people do in geodesy or CMB. I need to find the boundaries of this figure quickly and efficiently. It is an absolute must for me. Thank you, --AboutFace 22 (talk) 22:42, 1 December 2014 (UTC)[reply]

You already have (implicitly from previous discussion) a very efficient means of finding the (shorter) great circle arc between two points, for determining which side a point is of a given great circle (and indeed exactly how far it is from it), and for generating points at chosen distances along any such arc. With the disclaimer that I am not familiar with specialized numerical integration methods, I can't see what else you might need. If, for example, you have a rectangle projected onto a sphere (as from the original thread), you could rule it with great-circle arcs in any direction (e.g. on lines on longitude, independent of the orientation of the rectangle), choose points on those arcs, and use these for surface integration. Alternatively, your algorithm could choose points, which could be easily tested for being within a rectangle, via the sign of four dot products, one for each edge. The vectors that represent the boundaries are readily found from the four vertices (via the cross product). What is there missing from this? —Quondum 02:08, 2 December 2014 (UTC)[reply]

Thank you. "which could be easily tested for being within a rectangle, via the sign of four dot products, one for each edge" is one of the cutest ideas I've heard here so far. Never crossed my mind and it is very easy to do. I may not have edges though, I have corners. I have solved the same problem, however, by applying the British Flag Theorem. When the point is within the rectangle the sums of the square of the distances from the point to the corners $AP^{2}+CP^{2}=BP^{2}+DP^{2}$ obey some magnitude constraint. But your method which I hope will work, is more elegant. Perhaps you are right. I may have almost everything I need to start coding. Thank you, again, - --AboutFace 22 (talk) 02:40, 2 December 2014 (UTC)[reply]

Sorry for revisiting the issue with a negative comment but dot products the way you've suggested do not work at all. No angle changes sign at all. Even before I coded and did computations I began to doubt. To make things clear I want to provide a detailed description. In this simplest case I have a rectangle on a 2-sphere. The sphere diameter is 1.0. The rectangle is centered at the North Pole, meaning that the point where diagonals of the rectangle intersect coincides with the North Pole. Thus I will have four vectors from the center of the sphere to the corners of the rectangle:

\mathbf {X_{1}} ,\mathbf {X_{2}} ,\mathbf {X_{3}} ,\mathbf {X_{4}}

. I then have a fifth vector, the "test" or operational (moving) vector I need to evaluate:

\mathbf {X_{5}}

. In particular I want to know if it is located inside of the rectangle or outside. So, I define a dot product between this moving vector and four previous vectors as follows:

\mathbf {X_{1}} \cdot \mathbf {X_{5}} =cos\theta

. I omitted the vector norms in the denominator because they are a unit anyway. So, finally:

cos\theta =\sum _{k=1}^{3}X_{k}^{(1)}\cdot X_{k}^{(5)}

. After a dot product was computed with the three remaining vectors I got reverse cosines and added them together. None of the angles (arcs) changed signs when I moved the vector

\mathbf {X_{5}}

outside of the rectangle. The sum of all angles likewise never changed sign. One remarkable thing I observed: The sum of all angles (reverse of dot products) did not depend on angle φ of

\mathbf {X_{5}}

, only on angle θ to a remarkable degree, up to 15 decimal digits. Thanks, --AboutFace 22 (talk) 18:23, 3 December 2014 (UTC)[reply]

Maybe I'm confused because you seem to say several different things, but if you want to describe an arc from $\mathbf {X_{1}}$ and $\mathbf {X_{2}}$ can't you just say that:

\mathbf {A_{3}} =s\,\mathbf {X_{1}} +(1-s)\,\mathbf {X_{2}}

and

\mathbf {X_{3}} ={\mathbf {A_{3}}  \over \lVert \mathbf {A_{3}} \rVert }R

where s is an arbitrary new parameter that runs from 0 to 1 and R is the radius of the sphere. Then in a cartesian representation $\mathbf {A_{3}} (s)$ describes a secant through the the sphere, and the rescaling projects that path to the surface, hence defining an arc. It will break down if the starting points are exact antipodes, but that case if pretty ill-defined anyway.

This can be extended to the case of a rectangle defined by $\mathbf {X_{1}} ,\mathbf {X_{2}} ,\mathbf {X_{3}} ,\mathbf {X_{4}}$ by introducing a second parameter t:

\mathbf {A_{5}} =t(s\,\mathbf {X_{1}} +(1-s)\,\mathbf {X_{2}} )+(1-t)(s\,\mathbf {X_{3}} +(1-s)\,\mathbf {X_{4}} )

and

\mathbf {X_{5}} ={\mathbf {A_{5}}  \over \lVert \mathbf {A_{5}} \rVert }R

Assuming that the natural edges of the rectangle are $\mathbf {X_{1}}$ to $\mathbf {X_{2}}$ , $\mathbf {X_{2}}$ to $\mathbf {X_{4}}$ , $\mathbf {X_{4}}$ to $\mathbf {X_{3}}$ , and $\mathbf {X_{3}}$ to $\mathbf {X_{1}}$ .

It is worth noting that a uniform sampling of s and t, will not uniformly sample the surface of the sphere (especially if the points are far apart), but it is a good starting point. Dragons flight (talk) 19:29, 3 December 2014 (UTC)[reply]

Again it is my wont to acknowledge the contribution and thank you but I am now involved in an entirely different operation and will be able to think about it much later, perhaps even tomorrow. --AboutFace 22 (talk) 20:47, 3 December 2014 (UTC)[reply]

When you get to it, to be a little more explicit:

Take the four vectors to the corners of the rectangle as X₁, X₂, X₃, X₄ (in say anticlockwise order).
Find the four vectors representing each edge of the rectangle using the cross product: A₁₂ = X₁ × X₂, A₂₃ = X₂ × X₃, A₃₄ = X₃ × X₄, A₄₁ = X₄ × X₁.
Now find the four dot products that I was referring to: d₁₂ = X₅ ⋅ A₁₂, d₂₃ = X₅ ⋅ A₂₃, etc.
When all four are positive (or is it all negative?), X₅ is inside the rectangle.

—Quondum 20:58, 3 December 2014 (UTC)[reply]

Quondum, thank you very much. I checked your method, computed all cross and dot products and found that you are correct. When I moved the test vector X₅ outside of the rectangle at least two of the dot products turned negative. Inside of the rectangle they are all positive. It is already kind of late and I ran only one test. Tomorrow I will try to get a broader picture. I am very excited. This time you explained everything step by step and clearly. Thank you again.

Tomorrow I will check the other method, by Dragons flight. I need more than one method plus every method also offers other options for my handling integration on the sphere, perhaps other ways to verify some results and a better understanding of the task. --AboutFace 22 (talk) 03:14, 4 December 2014 (UTC)[reply]

Now I want to thank Dragons Flight. I checked the first formula (with three vectors) and it worked. Very helpful computationally and especially for this task where I feel, at this stage at least, that I am a blind person trying to identify and sort out good apples in a basket. Tomorrow I will check the second formula with five vectors. It is a cute stuff, very helpful and I am very excited. Thank you everyone. --AboutFace 22 (talk) 01:03, 5 December 2014 (UTC)[reply]

Dragons flight, the second formula works even better. Thank you, --AboutFace 22 (talk) 01:17, 6 December 2014 (UTC)[reply]

Just at the moment when I felt the post could be marked "SOLVED," which I have no idea how to do, I realized I have more questions. They are pertaining to Dragons flight's two formulas. I coded both in GFortran and tried to "play" with parameters. Both formulas work but now I have some questions regarding the second one. The first formula is straightforward because of just a single parameter s and does not require any explanation. With the second formula I don't have a clear picture where the vector $\mathbf {X_{5}}$ wanders. I am thinking about creating a file with samples of s and t and plotting the result as a 2-dimensional surface (if it is a surface!?) in 3-D space, just in Cartesian coordinates. At the same time, I wonder if there might be simple algorithmic statements like: if the values of s and t are (0.5,1.0), for example, then the vector $\mathbf {X_{5}}$ will be at a certain point, etc. In fact the computation shows that with parameters I have for the four corners of the rectangle (I can post them but don't think it is necessary) and parameters s and t as above, the computation gives the following position of the vector $\mathbf {X_{5}}$ : $\theta =0.76;\psi =-90.0$ . It looks like the vector $\mathbf {X_{5}}$ projection on equatorial plane coincides with the negative direction of the Y axis. So, I wonder if by just looking at formula 2 one can say something about the test vector $\mathbf {X_{5}}$ behavior. I hope I made my problem clear. Thanks, - --AboutFace 22 (talk) 18:33, 6 December 2014 (UTC)[reply]

I believe that you are asking about :

\mathbf {A_{5}} =t(s\,\mathbf {X_{1}} +(1-s)\,\mathbf {X_{2}} )+(1-t)(s\,\mathbf {X_{3}} +(1-s)\,\mathbf {X_{4}} )

and

\mathbf {X_{5}} ={\mathbf {A_{5}}  \over \lVert \mathbf {A_{5}} \rVert }R

.

Increasing s moves you towards X₁ & X₃ and away from X₂ & X₄; decreasing s does the opposite.

Increasing t moves you towards X₁ & X₂ and away from X₃ & X₄; decreasing t does the opposite.

So X₅ equals X₁, X₂, X₃, & X₄ when (s,t) equals (1,1), (0,1), (1,0), & (0,0) respectively.

For your specific example of (s,t) = (0.5,1.0), t=1.0 tells you that X₅ is on the line between X₁ & X₂; s=0.5 tells you that it is half along that line. -- ToE 02:37, 7 December 2014 (UTC)[reply]

     t
     ^
     |
   1 X2   X5   X1
     |
     |
     |
     |
     X4--------X3->s
               1

ASCII art to the rescue? -- ToE 02:49, 7 December 2014 (UTC)[reply]

ToE, thank you. You are correct, I was thinking about that (second) expression. What you are saying coincides with my computed data but only partially. I've made a table with key pairs (s,t) and looking at your statements, I can see that (1,1), (0,1) in my table are exactly as you said, (0,0) gives me the position of the vector $\mathbf {X_{5}}$ exactly as (0,1), the same corner of the rectangle and (1,0) is completely out of whack. It has $\theta =114.0;\psi =26.0$ , (all angles are in degrees), $\psi$ angle is correct but the $\theta$ Is not. The way I set up the rectangle on the sphere, $\theta$ should not exceed 1.76°. For this combination of ( $\theta ,\psi$ ) the test vector points to the south. All other combinations seems to have given me reasonable values except (0.75,0), (1,0.25) and (1,0.75) and of course (1,0) I just mentioned. Their polar angles exceed the maximum value for the rectangle, so the test vector wanders outside of the area I want it to stay in.

Sure, computer coding is inherently prone to errors and I will check everything more than once, however the fact that I have some coincidences tells me that it is quite likely the code is basically correct. I appreciate your help, --AboutFace 22 (talk) 17:04, 7 December 2014 (UTC)[reply]

These parametric formulas are simple and straight forward. Just plug in some ones and zeros for s and t to see how they work at their extremes.

(s,t) = (0,1) => 1(0 X₁ + 1 X₂) + 0(0 X₃ + 1 X₄) = X₂.

(s,t) = (0,0) => 0(0 X₁ + 1 X₂) + 1(0 X₃ + 1 X₄) = X₄.

Something is funny with your code (or your vectors) if they are coming out equal. Get these corner cases working first, as they are easiest to test and debug. -- ToE 17:40, 7 December 2014 (UTC)[reply]

You mean I've got my work cut out for me :-) Will try to find what's wrong. Thank you much, - --AboutFace 22 (talk) 18:07, 7 December 2014 (UTC)[reply]

Yes, there was an error. As usual, I don't even know where. I simply rewrote key parts with considerable simplifications. Everything appears to work as you said it should with one "problem," I don't even know if it is a problem or not: for every t=0.5 regardless of s the test vector's polar angle

\theta

equals 0, meaning it is at the North Pole. Again, thank you for your help. - --AboutFace 22 (talk) 19:10, 7 December 2014 (UTC)[reply]

Sounds like a problem to me. Good luck!

In case you've not worked with parametric equations before, here is a trick which might help you picture what is going on. Dragons Flight's first equation,

\mathbf {A_{3}} =s\,\mathbf {X_{1}} +(1-s)\,\mathbf {X_{2}}

and

\mathbf {X_{3}} ={\mathbf {A_{3}}  \over \lVert \mathbf {A_{3}} \rVert }R

, can be rewritten as

\mathbf {A_{3}} =\mathbf {X_{2}} +s\,(\mathbf {X_{1}} -\mathbf {X_{2}} )

. I assume that you follow the algebra, but do you see what it means? A₃ is equal to X₂ plus some fraction s of the distance (actually the vector X₁ - X₂) between X₂ and X₁. Thus A₃(s) steps you along the chord (or secant line) between X₂ and X₁.

I mention this partly because earlier you mentioned integration. For a fixed ∆s, A₃ will differer by fixed amounts as it walks across the secant line. But X₃, the renormalized A₃, walks along the great circle connecting X₂ and X₁, and its movement will not be constant with a fixed ∆s. This is easy to account for, but it is a simple trap to get caught in. -- ToE 19:50, 7 December 2014 (UTC)[reply]

ToE, thank you again. Actually Dragons Flight or someone else (I cannot immediately recall now) mentioned that the equal steps along the secant line will not project into equal steps along the arc of the great circle. It is easy to visualize actually, I had no problem with that. The integration points which are zeroes of Legendre Polynomials (in one variant, actually, they may be Laguerre, etc.) are not equally distributed either, so I've been thinking of perhaps making a reverse calculation: to map polynomial zeroes on the arc first and drop normals to the secant line if I can figure out how to do it, if not I will post here again. This way I will have a table of corresponding values because I will most likely use a method with a fixed number of zeroes, perhaps 20. In addition I will have to find out why the test vector comes to the North Pole. You and other guys helped me a lot. Wikipedia is a great place. --AboutFace 22 (talk) 23:08, 7 December 2014 (UTC)[reply]