Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

September 19

Cohen and the axiom of choice

The article on Paul Cohen mentions that:

Cohen is noted for developing a mathematical technique called forcing, which he used to prove that neither the continuum hypothesis (CH), nor the axiom of choice, can be proved from the standard Zermelo–Fraenkel axioms (ZF) of set theory.

I am trying to find out the exact year in which Coehn first proved the result concerning the axiom of choice (not the continuum hypothesis) and the year and the paper when it was first published, if ever. Thanks--Shahab (talk) 11:21, 19 September 2012 (UTC)

In 1963 according to this:

In 1942 Gödel attempted to prove that the axiom of choice and continuum hypothesis are independent of (not implied by) the axioms of set theory. He did not succeed, and the problem remained open until 1963. (In that year, Paul Cohen proved that the axiom of choice is independent of the axioms of set theory, and that the continuum hypothesis is independent of both.)

It was published in two parts, but the result had previously appeared in april 1963 and were presented may 3, 1963 at Princeton, according to the booknote at end of second paper: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC300611/?page=6

First paper: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC221287/?page=1

To work out where exactly the independence of ZFC of the axiom of choice is proven, I would first have to figure out what all this means...

Other info: http://www-history.mcs.st-andrews.ac.uk/Biographies/Cohen.html Ssscienccce (talk) 17:26, 19 September 2012 (UTC)

Solve this please

(Moved by User:JackofOz from Miscellaneous Ref Desk)

Questions 1 - 5

There are six soccer teams - J, K, L, M, N and O - in the Regional Soccer League. All six teams play each Saturday at 10 a.m. during the season. Each team must play each o f the other teams once and only once during the season.

Team J plays team M first and team O second.
Team K plays team N first and team L third.
Team L plays team O first.

On the first Saturday, which of the following pairs of teams play each other ?

(A)    J and K ; L and O ; M and N
(B)    J and K ; L and N ; M and O
(C)    J and L ; K and N ; M and O
(D)    J and M ; K and L ; N and O
(E)    J and M ; K and N ; L and O

Which of the following teams must K play second ?

(A)    J
(B)    L
(C)    M
(D)    N
(E)    O

What is the total number of games that each team must play during the season ?

(A)    3
(B)    4
(C)    5
(D)    6
(E)    7  

— Preceding unsigned comment added by 175.110.112.185 (talk) 19:43, 19 September 2012 (UTC)

You are essentially told the answer to the first question directly. I'm tempted to say it's obviously (E) (can you see why that's the case?)

Question two is done by process of elimination. K does not play N or L second because it plays them first and third respectively. J and O compete against each other in the second match so neither of them can play K. So the answer is M.

The answer to the third question is 5, obviously. For each other team, there are 5 other teams, and each team must compete against each other team exactly once. Widener (talk) 20:22, 19 September 2012 (UTC)

Creating a chart typically helps on this type of problem:

        O P P O N E N T S
TEAM   1st 2nd 3rd 4th 5th
----   --- --- --- --- ---
 J
 K
 L
 M
 N
 O

Try filling that in with what you know already. (Although, this doesn't look like so much of a logic problem as a reading comprehension problem.) StuRat (talk) 00:37, 20 September 2012 (UTC)

Show that a series is not Absolutely convergent.

Show that this series is not absolutely convergent: $\sum _{n\neq 0}e^{inx}{\frac {1}{2\pi in}}(e^{-inb}-e^{-ina})$.

This is my approach:
$\sum _{n\neq 0}\left|e^{inx}{\frac {1}{2\pi in}}(e^{-inb}-e^{-ina})\right|$
$=\sum _{n\neq 0}{\frac {1}{2\pi n}}\left|(e^{-inb}-e^{-ina})\right|$
This is almost the harmonic series. The desired result follows if you can show that $\left|(e^{-inb}-e^{-ina})\right|>c$ for some $c>0$ for every $n$ in an arithmetic progression, for example. Equivalently,
$\left|(e^{-inb}-e^{-ina})\right|>c$
$\iff 1\left|(e^{-inb}-e^{-ina})\right|>c$
$\iff |e^{ina}|\left|(e^{-inb}-e^{-ina})\right|>c$
$\iff \left|(e^{in(a-b)}-1)\right|>c$
might be easier to show.
$\iff \left|(\cos(n(a-b))+i\sin(n(a-b))-1)\right|>c$
Then it suffices that $\sin(n(a-b))>d$ for all $0<d<1$ for all $n$ in an arithmetic progression which is why I asked a similar question a while ago. That way, the number inside the absolute value signs will always have a nonzero imaginary part and therefore will have nonzero absolute value. It's not actually enough that $\sin(n(a-b))>d$ for infinitely many $n$ as I later realized, for instance the result doesn't (at least not obviously) follow if its only true for the squares.
Anyway, do you have suggestions for proving this result? — Preceding unsigned comment added by Widener (talk • contribs) 20:07, 19 September 2012 (UTC)

exp(-i n b) - exp(- i n a) =

exp[-i n (a+b)/2] {exp(i n (a-b)/2) - exp(-i n (a-b)/2)}

So, the summation of the absolute value of the terms is:

${\frac {2}{\pi }}\sum _{n=1}^{\infty }{\frac {\left|\sin \left[{\frac {(a-b)n}{2}}\right]\right|}{n}}$

If you replace infinity by N in the upper limit, you can say that the value is larger than what you get if you replace the absolute value of sin by sin^2. Then you can write sin^2 in terms of cos of the double argument, this yields one divergent summation (in the limit of N to infinity) and a convergent summation. Count Iblis (talk) 20:55, 19 September 2012 (UTC)

Hey, that works! Thanks! Widener (talk) 21:16, 19 September 2012 (UTC)

The maze on today's main page.

As I posted earlier on Wikipedia:Main Page/Errors, the caption for this was a little confusing. Can anyone here figure out what it was trying to say: "In these mazes, it will typically be relatively easy to find the origin point, since most paths lead to or from there, but it is hard to find the way out"? As far as I can tell, since everywhere is connected to everywhere else, and there is neither a marked 'start' or 'end' once the maze is constructed, the statement makes no sense.

Incidentally, I'm fairly sure that there is a name for this particular type of maze - it has no 'loops' so can be navigated in its entirety simply by 'following a wall' - does anyone know the name? AndyTheGrump (talk) 21:08, 19 September 2012 (UTC)

It sounds like the "all roads lead to Rome" concept. In the case of the Roman Empire, all roads would actually also lead to any connected city. What they are really saying is that it's the central hub. Think of it like an airline's hub city, too. Yes, you can get to any city they service eventually, but the direct routes all lead to or from the hub city. StuRat (talk) 00:34, 20 September 2012 (UTC)

The phrase "simply connected" comes to mind, and it would technically be correct for a certain view of this (no loops) maze, although I'm not sure if anyone in the maze community uses precisely that term. (Although simple graph would be more relevant from a graph theory perspective.) I would also imagine (though don't have any proof/calculations to show) that the depth-first generation method would produce a maze with a low average degree of branching, which should aid in maze traversal, though I don't know if it would differentially affect and given position. Although it might be that since branching preferentially happens at the tips of the growing maze, you might expect a gradient of degree, with points near the origin having lower average degree than those further from it, leading to search being simpler in the region of the starting point. -- 205.175.124.30 (talk) 02:11, 20 September 2012 (UTC)

It appears that "perfect maze" is the most common name for loop-free mazes. -- BenRG (talk) 06:10, 20 September 2012 (UTC)

Why you force SSL in the HTTP link...? http://www.google.com/search?q=perfect+maze
See also directly pages Maze and Maze solving algorithm, they both say the same: Mazes containing no loops are known as "standard", or "perfect" mazes, and are equivalent to a tree in graph theory. --CiaPan (talk) 05:23, 21 September 2012 (UTC)

Why you force unsecure plaintext in the HTTP link? Nil Einne (talk) 13:32, 25 September 2012 (UTC)

Beacuse it doesn't need any 'security' and there's no reason to hide it. There's nothing secret in using Google search machine or in the query itself or in its results. Additionally pasting the plain URL makes it easier for readers to see where they are directed. It is also short enough, so it does not disturb in reading surrounding text. --CiaPan (talk) 15:25, 25 September 2012 (UTC)

September 20

Lanchester's Law and Game Theory

Let us consider Lanchester's square law and three groups A,B,C which want to go to war. Making up numbers, let's say A,B,C have armies of sizes 45, 40, and 35 respectively. I am concerned with the optimal strategy for group C. From what I understand, B and C should form an alliance. They'll have a vastly superior force than A. They will beat A and both B and C will suffer casualties in proportions. After A has been beaten, then B and C can fight each other. It seems to be that if C has the smallest army, then it will always lose in the end. A,B,C can randomly all shoot at each other or B and C can form an alliance, wipe out A, and then turn against each other. Is there ever an case (with army sizes being A < B < C...notice strict inequalities) where Lanchester's Law and Multiparty Game Theory predict that C will win? A numerical counterexample is what I am looking for of course. If not then, C will always lose, right? So what is C to do? What incentive is there for C to form an alliance with B? It knows it will be killed in the end anyway so why help B (over A) survive? Is this the best strategy? If yes, then why because C's destruction seems inevitable so why should C care what it does and who it helps and what strategy it chooses? - Looking for Wisdom and Insight! (talk) 04:59, 20 September 2012 (UTC)

I assume you meant "A > B > C" Dbfirs 07:54, 20 September 2012 (UTC)

I can see three possible winning strategies for C:

1) The obvious one is to make peace with both A and B.

2) Form an alliance with one and hope that it holds after the other is defeated.

3) The most Machiavellian way for C to win is to secretly instigate a war between A and B, then, after one is destroyed and the other is weakened, attack. StuRat (talk) 05:18, 20 September 2012 (UTC)

See truel for something very similar. Since peace treaties as unnecessary between friends I view them as declarations of war but not yet. Option 3 certainly seems the best option for C, the problem is what happens if A or B discover it. C could also send an army of size 5 to 'help' B. It would be interesting to try and figure out the strategies to stay alive the longest if they are all fighting each other. Say army A devoted a(t) of its effort to destroying B and 1-a(t) to destroying C, so C was being destroyed by a force of A(1-a(t))+Bb(t), B by a force of C(1-c(t))+Aa(t) and A by B(1-b(t))+Cc(t). Dmcq (talk) 12:40, 20 September 2012 (UTC)

Peace should break out all over in ABC world, for no one can afford to attack alone, nor be the weaker ally in an attack. Rich Farmbrough, 21:10, 20 September 2012 (UTC).

Yep as far as I can see if they have a three way war then all three will be completely destroyed at the same time if the two smaller ones could defeat the largest. What'll happen is that the smaller ones will gang up on the largest until it is no longer the largest, then the two larger will reduce each other till all three are the same size as the smallest. Dmcq (talk) 22:31, 20 September 2012 (UTC)

League problem

Resolved

For a game I'm trying to come up with a particular league system, and I'm unsure how to go about doing it. I tried to do it manually but I couldn't come up with an algorithm that led me to a solution. Basically I have 16 teams in a league, but for logistics' sake I need to break it up into four 4-team series. I figure if I can break it up right, then I can each team have faced every other team in one of the series once, and only once. So in the first leg I have four series:

Series 1	Series 2	Series 3	Series 4
Team A	Team E	Team I	Team M
Team B	Team F	Team J	Team N
Team C	Team G	Team K	Team O
Team D	Team H	Team L	Team P

Each team has to face 15 other teams, and in each leg it faces 3 other teams, so then in 5 legs any given team will have faced all 15 other teams. I can come up with two other legs: one by simply flipping it around the diagonal (so Series 1 would be teams A, E, I, and M), and the other by taking diagonals for each series (so Series 1 would be teams A, F, K, and P), but beyond that I start running into problems. Maybe I'm backing myself into a corner, I don't know. And I calculate that there are 2386 possible ways to sort the 16 teams into 4 series, so I'm not about to check all of those, to find five "orthogonal" legs.

Is there a better way of going about this, in a more mathematical way? Thanks —Akrabbim^talk 16:47, 20 September 2012 (UTC)

I think your approach is reasonable. Your 4th and 5th groups will be "what's left":

Series 1	Series 2	Series 3	Series 4
Team A	Team E	Team I	Team M
Team B	Team F	Team J	Team N
Team C	Team G	Team K	Team O
Team D	Team H	Team L	Team P

Series 1	Series 2	Series 3	Series 4
Team A	Team B	Team C	Team D
Team E	Team F	Team G	Team H
Team I	Team J	Team K	Team L
Team M	Team N	Team O	Team P

Series 1	Series 2	Series 3	Series 4
Team A	Team E	Team I	Team M
Team F	Team J	Team N	Team B
Team K	Team O	Team C	Team G
Team P	Team D	Team H	Team L

 .
 .
 .

Also note that there are many possible solutions. StuRat (talk) 17:12, 20 September 2012 (UTC)

But the other diagonal will intersect. One direction will be A,F,K,P, and the other direction will be A,N,K,H. A and K are in both. —Akrabbim^talk 17:29, 20 September 2012 (UTC)

Yes, you're right, I've revised my advice above. I'm going to write a program to solve this and post it tomorrow. StuRat (talk) 17:38, 20 September 2012 (UTC)

Thanks, I'll be interested to see what you come up with and your algorithm to solve it. I was trying to work it out with Matlab, but it was just turning into a clumsy brute force algorithm, and I wasn't getting anywhere. But I charted it out, and three legs that we have here are definitely not part of the solution. For example, for A and G to meet, the only teams that haven't met A and G would be J and N, and they have both played each other already, so I right when I thought I had painted myself into a corner. —Akrabbim^talk 17:56, 20 September 2012 (UTC)

(Teams have numbers rather than letters, obviously)

Series 1: 1, 2, 3, 4
Series 2: 5, 6, 7, 8
Series 3: 9, 10, 11, 12
Series 4: 13, 14, 15, 16

Series 1: 1, 5, 9, 13
Series 2: 2, 6, 10, 14
Series 3: 3, 7, 11, 15
Series 4: 4, 8, 12, 16

Series 1: 1, 6, 11, 16
Series 2: 2, 5, 12, 15
Series 3: 3, 8, 9, 14
Series 4: 4, 7, 10, 13

Series 1: 1, 7, 12, 14
Series 2: 2, 8, 11, 13
Series 3: 3, 5, 10, 16
Series 4: 4, 6, 9, 15

Series 1: 1, 8, 10, 15
Series 2: 2, 7, 9, 16
Series 3: 3, 6, 12, 13
Series 4: 4, 5, 11, 14

81.159.104.182 (talk) 03:41, 21 September 2012 (UTC)

You beat me too it, 81. Yes, that's a valid solution. 81's version of diagonals in the third grouping seems to work, while mine does not. (Running my program, I found one solution given his first 3 groupings, and no solution given my first 3 groupings.) StuRat (talk) 06:17, 21 September 2012 (UTC)

BTW, Akrabbim, where did the 2386 number come from ? My program seemed to come up with 2,627,625 possible groupings. Here's the formula:

16!
---
4!5

StuRat (talk) 06:36, 21 September 2012 (UTC)

(formerly 81.159) I agree: 16!/(4!^5). I don't understand where that 2386 number comes from either. 86.160.216.189 (talk) 11:28, 21 September 2012 (UTC)

Hey, that's great! Thanks! Can I ask how you figured it out? And about the 2386: I was thinking it would be choose 4 for the first group, then 4 for the next group from the remaining, and so on. So (16/choose/4) * (12/choose/4) * (8/choose/4) * (4/choose/4) = 1820 * 495 * 70 * 1 = 63,063,000 (when I first punched it in accidentally did + instead of *, which is where I got 2386). I haven't thought about probability at all in years though, so I'm not surprised I'm wrong. —Akrabbim^talk 14:34, 21 September 2012 (UTC)

Arrangements in which the split into groups is the same but groups are listed in a different order are counted separately in your count, but only count as one arrangement in StuRat's count. So your count is 4! = 24 times as large as StuRat's count. Gandalf61 (talk) 14:40, 21 September 2012 (UTC)

Agreed, there are the 24 ways to arrange the series, but those are all equivalent. For example, these two are equivalent:

Series 1	Series 2	Series 3	Series 4
Team A	Team E	Team I	Team M
Team B	Team F	Team J	Team N
Team C	Team G	Team K	Team O
Team D	Team H	Team L	Team P

Series 4	Series 3	Series 2	Series 1
Team A	Team E	Team I	Team M
Team B	Team F	Team J	Team N
Team C	Team G	Team K	Team O
Team D	Team H	Team L	Team P

As to the method I used, it wasn't very elegant, I just used brute force. Can we mark this Q resolved ? StuRat (talk) 16:31, 21 September 2012 (UTC)

"when I first punched it in accidentally did + instead of *" ... Ooops!! 86.160.216.189 (talk) 17:28, 21 September 2012 (UTC)

Thanks everybody, yes it is resolved. —Akrabbim^talk 01:09, 25 September 2012 (UTC)

x/y in IV quadrant, is the given ratio negative or positive?

question: "Suppose that the point (x,y) is in the indicated quadrant (IV). Decide whether the given ratio is positive or negative." Is it not positive, simply by sketching? How would it be negative? thanks.24.139.14.254 (talk) 20:08, 20 September 2012 (UTC)

Just look at the signs of x and y. The ratio of two numbers with the same sign is positive; the ratio of two numbers with opposite signs is negative. Widener (talk) 20:28, 20 September 2012 (UTC)

September 21

Integration of 1/x in Quadrant I

Hi. First of all, this isn't an actual homework problem, but a conceptual question I asked a mixed crowd of people, some of whom know integration techniques and some of whom which who whom don't. Everybody seemed to know intuitively or by proof that the area underneath the curve in quadrant one is infinite, because since the graph never touches either axis, the area underneath each section is infinite. This didn't make sense to me, because I intuitively compared it to a converging sum such as 0.999..., but apparently the hyperbolic function does not converge. Therefore, I must be severely deluded. The integration technique also relies on the fact that zero invalidates the integration, resulting in infinity; if one of the axes were shifted away from the zero-point, the area would still be infinite. This brings up the question: since shifting both axes away from zero would immediately cause the function's area to become finite, is there a tipping point of some sort? This is hillarious because the hyperbola itself is tipping pointential. Therefore, perhaps at the exact tipping point upon which the area oscillates between finite and infinite, causing the creating of a complex number. However, since this is a bi-axial method, the convergence paradigm is both null and void.

I must admit, quite embarrassingly, that I've never done mathematical proofs for more than one hour in my entire life. Therefore, I may need to rely on intuitive techniques such as visual calculus to get the point across to myself about why this function has an infinite area. I incorrectly assumed that the total area underneath the hyperbola in the first quadrant is reducible to be equivalent to the area to the bottom left of a linear function with the slope -1. However, I then remembered my Cartesian plane-onto-sphere method, which was improperly answered because my method assumes an infinite Cartesian surface, whereas stereographic projection relies on a finite Earth. It would be more like taking the membrane of an open universe and reconstructing it to make it closed. Anyway, I proved to myself that in this projection, the four points of (0,0), (x-fin,x-infinlim), (y-fin,y-infinlim) and (±∞,±∞) together comprise the manifold geodesic of a sphere in 2.5 dimensions (clarification, citation, objectivity and sanity needed), in each of the four quadrants (actually, there are a total of eight). This is where {x,y-fin/infinlim} form the continuum where the grid system transforms from finite in one direction to infinite in the opposite direction (from the vantage point of the "anti-origin"), forming two points on a sort of central meridian line, though that's irrelevant largely to solve this problem. So in the Q-I space, the first quadrant forms a circle, and that circle's area is infinite. The perimeter of this circle must also be infinite. The area under the hyperbola, thus, represents an area around the circumference of this circle, although it is widest at one point of the circle and converges at the other end of the circle. Despite the distance from this circumference getting smaller as the function recedes from the 2-space origin, the area still goes onto infinity, thus allowing the total area by integration to be infinite. Phew, though this is not as clear to most people, so there has to be a better intuitive way of proving it.

Someone enlighten me by dialing 0 on the Hamiltonian operator. Thanks. ~AH1 ^(discuss!)

If you're having trouble seeing that the area under the curve y = 1/x in the first quadrant is infinite, consider the following picture, similar to those commonly drawn to illustrate Riemann sums:

All of the blue rectangles are included in the area under the red curve y = 1/x, so the area under the curve must be at least as large as the total area of all the rectangles. Every rectangle has width 1. The first rectangle has height 1, the second has height 1/2, the third has height 1/3, and so on. So the total area of the rectangles is the sum of the harmonic series 1 + 1/2 + 1/3 + …, and this sum is infinite:

${\begin{aligned}A_{\textrm {rect}}&=1+{\frac {1}{2}}+\left({\frac {1}{3}}+{\frac {1}{4}}\right)+\left({\frac {1}{5}}+{\frac {1}{6}}+{\frac {1}{7}}+{\frac {1}{8}}\right)+\left({\frac {1}{9}}+{\frac {1}{10}}+{\frac {1}{11}}+\cdots +{\frac {1}{16}}\right)+\cdots \\&\geq 1+{\frac {1}{2}}+\left({\frac {1}{4}}+{\frac {1}{4}}\right)+\left({\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}\right)+\left({\frac {1}{16}}+{\frac {1}{16}}+{\frac {1}{16}}+\cdots +{\frac {1}{16}}\right)+\cdots \\&=1+{\frac {1}{2}}+{\frac {1}{2}}+{\frac {1}{2}}+\cdots .\end{aligned}}$

Since the total area of the blue rectangles is infinite, the area under the curve y = 1/x must also be infinite. —Bkell (talk) 08:21, 21 September 2012 (UTC)

See also Gabriel's Horn for the nice paradox that the "horn" formed by rotation of y = 1/x (x>1) about the x axis has finite volume but infinite area, so it can be filled with paint but its surface can't be painted. AndrewWTaylor (talk) 09:51, 21 September 2012 (UTC)

Good example, but Gabriel's horn has x^2 in the denominator, and 1/x^2 has a finite integral from 1 to infinity. SemanticMantis (talk) 15:15, 21 September 2012 (UTC)

No, AndrewWTaylor was correct when he said that Gabriel's horn is constructed by rotating y = 1/x about the x-axis. The volume integral has a 1/x² in it, but that's not the defining curve. —Bkell (talk) 02:59, 22 September 2012 (UTC)

• Also, the "graph never touches either axis" is not a valid argument for infinite area, so perhaps your reticence to accept it was more correct than you knew! Consider a piecewise defined function, f=1/x^(0.5), x in (0,1), f=1/x^2, x in [1,infinity). This function has a finite integral over (0,infinity), and the graph never touches either axis. SemanticMantis (talk) 15:15, 21 September 2012 (UTC)

Limits of Integration

Is it true in general that $\lim _{n\rightarrow \infty }\int _{a(n)}^{b(n)}f(x,n)dx=\lim _{n\rightarrow \infty }\int _{\lim _{m\rightarrow \infty }a(m)}^{\lim _{m\rightarrow \infty }b(m)}f(x,n)dx$?


Widener (talk) 02:57, 21 September 2012 (UTC)

Consider
      $a_{n}=n,\ b_{n}=a_{n}+1,\ f=1\ \dots$
Or
      $a_{n}=0,\ b_{n}=n,\ f(x,n)={\tfrac {1}{n}}$
CiaPan (talk) 05:30, 21 September 2012 (UTC)

Good answer. Interchange_of_limiting_operations has scant information, and could use some improving if anyone is interested. SemanticMantis (talk) 15:03, 21 September 2012 (UTC)

Oh, of course, but what if you add the condition that the limits $\lim _{n\rightarrow \infty }a_{n}$ and $\lim _{n\rightarrow \infty }b_{n}$ exist? Widener (talk) 16:34, 21 September 2012 (UTC)

$a_{n}=-{\tfrac {1}{n}},\ b_{n}={\tfrac {1}{n}},\ f=n$. -- Meni Rosenfeld (talk) 17:04, 22 September 2012 (UTC)

Hm. Okay. I think it is true that $\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin t}{\sin(t/(2(N+1/2)))(N+1/2)}}=\int _{0}^{\pi }{\frac {\sin t}{t}}$ though.

If you can interchange the limit and integral somehow you get

$\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin t}{\sin(t/(2(N+1/2)))(N+1/2)}}$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin t}{(t/(2(N+1/2))+O(t^{3}/(8(N+1/2)^{3})))(N+1/2)}}$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin t}{t/2+O(t^{3}/(8(N+1/2)^{2})}}$

${\stackrel {?}{=}}{\frac {1}{2}}\int _{0}^{\lim _{N\rightarrow \infty }{\frac {\pi (N+1/2)}{N+1}}}\lim _{N\rightarrow \infty }{\frac {\sin t}{t/2+O(t^{3}/(8(N+1/2)^{2})}}$

$={\frac {1}{2}}\int _{0}^{\pi }{\frac {\sin t}{t/2}}=\int _{0}^{\pi }{\frac {\sin t}{t}}$

Widener (talk) 18:12, 22 September 2012 (UTC)

$\lim _{\epsilon \rightarrow 0}\int _{0}^{1-\epsilon }f(x,\epsilon )\,dx=\lim _{\epsilon \rightarrow 0}\int _{0}^{1}f(x,\epsilon )\,dx-\lim _{\epsilon \rightarrow 0}\int _{1-\epsilon }^{1}f(x,\epsilon )\,dx$

$=\int _{0}^{1}\lim _{\epsilon \rightarrow 0}f(x,\epsilon )\,dx-\lim _{\epsilon \rightarrow 0}\int _{1-\epsilon }^{1}f(x,\epsilon )\,dx$

If the integrand in the last integral is finite (bounded) in the neighbourhood (x,ε) → (1,0), then ... — Quondum 20:56, 22 September 2012 (UTC)

Inverse birthday problem

The birthday problem of course describes the probability that two people in a given set of people will share birthdays.

But what are the odds in a group of n people that there are days where there are no birthdays?

The birthday problem's solution implies that birthdays often cluster. Would that mean that unbirthdays are also clustered?

This isn't homework of any sort; I'm just curious. I have ~500 Facebook "friends" — what are the odds that none of them have a birthday today? --Mr.98 (talk) 13:39, 21 September 2012 (UTC)

Off the top of my head, I think this is easier than the birthday problem, because we don't have to be careful about things like Alice and Bob share some birthday, OR Alice and Charles share some birthday, etc... If we assume that birthdays are uniformly distributed, and each person's birthday is independent of all the others, then we can just multiply to answer your final question. Because they are uniformly distributed, the probability that person A's birthday is not today is 364/365. Likewise for person B. Because they are independent, we can multiply to get the probability that today is not A's birthday AND is not B's birthday is 364/365 X 364/365. So the probability (not odds) that no friend has a birthday today is (364/365)^500=0.2537. Note that your last question is different from your second (i.e. some B-day free day exists, vs today is a B-day free day); that one takes a little more work. SemanticMantis (talk) 16:15, 21 September 2012 (UTC)

More concisely, the last question is the same as "if 500 people roll a 365-sided die, what is the probability that none of them roll a 265 (today)", while the second question is "if n people roll a 365-sided die, what is the probability that there is some number which does not occur." SemanticMantis (talk) 16:20, 21 September 2012 (UTC)

It's not so easy to work out a formula, but the probability that there is some day with no birthday is near certainty until the number of people gets well up into the thousands. Looie496 (talk) 16:24, 21 September 2012 (UTC)

Isn't the chance that a day exists where nobody in a group of 365 or more has the same birthday given by 1-(1-(364/365)ⁿ)³⁶⁵ ? So, when n = 500, we get 1-(1-(364/365)⁵⁰⁰)³⁶⁵ = 1-(1-0.2537)³⁶⁵ = 1-(0.7463)³⁶⁵ = 1 - 4.1779×10^-47, or, for all practical purposes 1.0, a virtual certainty that at least one birthday-free day exists. Here's the calculations with different values of n plugged in:

  n     probability of a birthday-free day existing
-----   -------------------------------------------
  500   ≈1.0
 1000    0.99999999997
 1500    0.9975
 2000    0.78
 2500    0.32
 3000    0.093
 4000    0.0062
 5000    0.00040
 6000    0.000026
 7000    0.0000017
 8000    0.00000011
 9000    0.0000000069
10000    0.00000000044

StuRat (talk) 17:35, 21 September 2012 (UTC)

I am immediately suspicious of that formula 1-(1-(364/365)ⁿ)³⁶⁵ as it gives a smooth transition of probabilities at the point n = 365. 86.160.216.189 (talk) 17:59, 21 September 2012 (UTC)

It does seem odd that it gives a probability of almost 1, but not exactly 1, when used for fewer than 365 people. It's within 1.5×x10^-78 of 1, though. Is this the chance that the universe will end before the year ends ?  :-) StuRat (talk) 18:08, 21 September 2012 (UTC)

The formula is only an approximation, because it treats the days as independent, which they aren't really. Looie496 (talk) 18:40, 21 September 2012 (UTC)

In what sense ? I suppose birthdays aren't completely evenly distributed, in that slightly more people are born at some parts of the year than others. However, I don't think that's the issue here. StuRat (talk) 18:44, 21 September 2012 (UTC)

I agree with you StuRat, independence of birthdays is not the problem with your formula (that is why I phrased the problems with dice above, just to be clear about the assumptions.) Nevertheless, I also think your formula is wrong. Why should it be right? You haven't explained your reasoning at all. Also, you can easily write a program to get some good approximate answers. I bet if you do that (correctly), you'll get answers noticeably different from your table above. SemanticMantis (talk) 18:53, 21 September 2012 (UTC)

Well, if the chance of a given day being birthday free is 0.2537, then the probability that it has at least one birthday is 1-0.2537, or 0.7463. The chances of 2 such independent days having one or more birthday each then becomes 0.7463². The chances of 365 independent days having one or more birthday each then becomes 0.7463³⁶⁵. The chance of this not being the case then becomes 1-0.7463³⁶⁵. StuRat (talk) 19:07, 21 September 2012 (UTC)

I think I see what Looie means, though. Once we know that one day contains (or doesn't contain) a birthday, this can change the count of potential birthdays that can fall on the other dates. So, yes, in this sense my formula is an approximation, with an error under 1.5×x10^-78, in the case of 364 people. StuRat (talk) 19:12, 21 September 2012 (UTC)

I haven't actually checked anything numerically, but the fact that the formula is inexact, and the error bounds have not been mathematically quantified, leaves open the possibility that it is badly wrong for other values. The 1.5×10^-78 example by itself not necessarily confidence-inspiring. 86.160.216.189 (talk) 19:31, 21 September 2012 (UTC)

Consider the total number of ways to distribute the birtdays of the n persons over the 365 possible dates. You can represent each possible distribution as a string of the form

00|0|0000|0||00|0|00|....

where each "0" represents a birtday of the person and the "|" are the separations between different days. So, on Januari 1 you have two birtdays, on Januari 2 there is one birtday etc. etc. Then everyu possible string o can write down corresponds to a valid distribution and voce versa, so you just need to count the number of strings. We have n "0"'s and we have 364 "|"'s so the total number is Binomial[364 + n,n].

Then if we demand that on every day you have at least one birtday, then this means that you must leave at least one "0" at each position in the string. This means that you have n-365 "0"'s that you can freely shuffle around. You can, of course, also consider strings with n -365 "0"s, themapping between a birthday distribution is then the number of "0"'s at some date plus one. So, the total number of such distributions is Binomial[n-1,n-365].

The probability that you always have at least one birtday on each date is thus Binomial[n-1,n-365]/Binomial[364 + n,n], the probability that there are days where you don't have birthdays is thus given by:

1 - Binomial[n-1,n-365]/Binomial[364 + n,n]

Count Iblis (talk) 17:08, 21 September 2012 (UTC)

• I have doubts that this is correct. For a start, you seem to be assuming that your Binomial[364 + n,n] combinations are all equally likely, but it seems to me that they are not. 86.160.216.189 (talk) 17:46, 21 September 2012 (UTC)

  Yes, you are right, although it is easy to correct this by imposing an order on the birthdays. I'll correct the solution. Count Iblis (talk) 18:13, 21 September 2012 (UTC)

I corrected the above problem, I found that the probability p for there being one or more days on which there are no birthdays is given by:

$p=1-{\frac {1}{r^{n}}}\sum _{k=0}^{r}(-1)^{r-k}{\binom {r}{k}}k^{n}$

where r = 365

Count Iblis (talk) 19:50, 21 September 2012 (UTC)

What is k ? Also, would you like to run that against the numbers in my chart above, to see how the two compare ? StuRat (talk) 23:27, 21 September 2012 (UTC)

I tried it earlier and they seem to correspond quite well, so assuming Count Iblis' formula is correct, it seems like yours is a pretty good approximation after all. (As far as evaluating the formula is concerned, k is just an internal counter which does not need to be assigned a meaning, but probably you know that and are asking about its meaning in terms of the formula derivation.) 86.160.216.189 (talk) 00:17, 22 September 2012 (UTC)

Looks ok. There are $365^{n}$ possibilities. To get the ones with birthdays on every day, you have to subtract the ones where at least one day has no birthdays. There are $364^{n}$ ways to distribute them over 364 days, and 365 ways to choose those 364, so $365^{n}-365*364^{n}$; however, now you removed the ones with two "birthless" days twice. So you add those: there's ${\binom {365}{2}}$ ways to choose those days, giving you $365^{n}-365*364^{n}+{\binom {365}{2}}*363^{n}$. Same thing again: some are counted twice, so you must subtract ${\binom {365}{3}}*362^{n}$; repeat the same proces till you arrive at all birthdays on one day, divide by total number of possibilities gives the odds of all days having birthdays, subtract from 1 to get the odds you wanted. Ssscienccce (talk) 01:30, 22 September 2012 (UTC)

About the derivation, you can use inclusion/exclusion as Ssscienccce explained above. Another way is to directly evaluate evaluate the number of ways you can have one or more birthday on each date by summing over each distribution of the birth dates over the year. So, if there are $k_{j}$ birthdays on the jth date, then the total number of ways to have such a distribution is:

${\frac {n!}{\prod _{j=1}^{r}k_{j}!}}$

If we sum this over all possible values of $k_{j}$ we should find $r^{n}$. In the summation, you have to impose the constraint $\sum _{j=1}^{r}k_{j}=n$. You can do this using generating functions. You compute the function:

$f(x)=\sum _{k_{1}=0}^{\infty }\sum _{k_{2}=0}^{\infty }\cdots \sum _{k_{r}=0}^{\infty }{\frac {n!}{\prod _{j=1}^{r}k_{j}!}}x^{\sum _{j=1}^{r}k_{j}}$

The coefficent of x^n is then the desired answer. Taking out the factor n!, the summation factors into identical summations, and each summation is the series expansion of exp(x), so f(x) = n! exp(rx), the coefficient of x^n is thus r^n. If we now consider only cases where you have one or more birthdays on each date, then each of the summation starts at 1 instead of zero, so, you get f(x) = n! [exp(x) - 1]^r. The coefficient of x^n can be obtained by first expanding [exp(x) - 1]^r and then extracting the coefficient of x^n from each term, you then get the above formula.

You can also use the generating function directly to find approximations for large n, you can write the coefficient of x^n as the contour integral of f(z)/z^(n+1) around the origin and then using the saddle point method obtain approximations to that integral. Count Iblis (talk) 02:00, 22 September 2012 (UTC)

see Coupon collector's problem. Robinh (talk) 08:28, 23 September 2012 (UTC)

Sorry if I'm making a mistake here, but I think the formula

$p=1-{\frac {1}{r^{n}}}\sum _{k=0}^{r}(-1)^{r-k}{\binom {r}{k}}k^{n}$

is not correct. Let n=4 (number of people) and r=3 (number of days in the year). The number of ways to get at least one untaken day is the number of ways to get 2 untaken days (=3) plus the number of ways to get 1 untaken day (=3×2⁴), for a total of 51 out of 3⁴=81 possible arrangements. But the above formula gives

$1-{\frac {-0+3-3\cdot 16+81}{81}}$

due to the alternating signs term (-1)^r-k, whereas every term in the numerator except the last should have a minus sign. Duoduoduo (talk) 13:56, 23 September 2012 (UTC)

So, here the formula gives 15/27 for the probability. Let's then count the number of ways to arrange the 4 persons so that you have one or more untaken days. I can put all four on the same day, there are 3 ways to do that. Then I can divide the group of 4 into one group of 3 and one of one and put these two groups on two days. There are 4 ways to make two such groups and there are 3 ways to choose a day for the group of 3 and having made that choice, 2 ways to choose a day for the remaning person. So, there are a total of 4*3*2 = 24 ways for such a distribution. Finally we can divide the four into two groups of 2, there are binomial(4,2)/2! = 3 ways to do that (we divide by a symmetry factor of 2! so that interchanging the dates of the two groups yields configurations that are not already accounted for by the different ways one can divide the persons in the two groups). Given the two groups there are 3 ways to choose a date for one group and given that choice, 2 ways to chose a date for the other. So, there are a total of 3*3*2 = 18 such possibilities. There are thusa total of 3 + 24 + 18 = 45 possibilities, the probability is thus 45/81 = 15/27. Count Iblis (talk) 17:01, 23 September 2012 (UTC)

You're right--thanks! Duoduoduo (talk) 19:54, 23 September 2012 (UTC)

cells within a table

A	B
C	D
E	F
G	H

The above table has 2 columns and 4 rows. In the above example I have assigned 8 different values to the 8 cells of that table. Let us say that we can rearrange the values at will. By rearranging the values, how many different arrangements are possible? Bus stop (talk) 19:46, 21 September 2012 (UTC)

$8!=40320$ see permutation. Widener (talk) 21:53, 21 September 2012 (UTC)

Thanks, Widener. That number surprises me as I would have guessed a far lower number. By the way I see the number at Factorial. Bus stop (talk) 01:31, 23 September 2012 (UTC)

A

B

C

D

E

F

G

H

Followup question: Does the same calculation apply in the case of the above arrangement? Bus stop (talk) 11:06, 23 September 2012 (UTC)

Yes. The formula is not based on the physical arrangement. The idea is this: There are 8 choices for where to put A. After A has occupied a box, there are 7 choices for where to put B. So we could have had A in the first box and B in any of 7 other boxes, or we could have had A in the second box and B in any of 7 other boxes,...,so for each of 8 possibilities for A there are 7 possibilities for B, hence we have 8×7 possibilities so far. Then for each of those 8×7 possibilities there are 6 remaining possible choices for where to put C, giving 8×7×6 possibilities so far. And so on until the end, where we have 8×7×6×5×4×3×2×1 possibilities. Duoduoduo (talk) 13:36, 23 September 2012 (UTC) possibilities possibilities

Thank you. That is really interesting. I have to think about that. Bus stop (talk) 14:08, 23 September 2012 (UTC)

Friendship combinations

Let say there are 6 people: A, B, C, D, E, F. Each of them has 2 internet friends in the group. None of them has any internet friend outside of the group. How many different ways can this happen? I already know the answer which is 70 but I'm confused on how to find the answer. Can anyone explain to me in details how to get the answer? Thanks!65.128.190.136 (talk) 21:23, 21 September 2012 (UTC)

I find problems like this usually require some fiddling around. A special case is when you have two groups of three; there are $10$ of those. WLOG you can look at the group of three containing A - then you vary the other two. Widener (talk) 22:05, 21 September 2012 (UTC)

You could do this systematically by starting with A, then going through all possible pairs that could be both partnered with A. Then for each person in each of those pairs, you could go through all possible pairs that could be partnered with them - this process will terminate when you get back to someone you have already considered. That's the brute-force approach; there may be a quicker approach but I'm not aware of it off the top of my head. Widener (talk) 22:17, 21 September 2012 (UTC)

Think of the 6 people as points/nodes; friendship is designated by connecting two points/nodes. Given the condition that each person has exactly 2 friends, you need to connect them with lines so that every point/node is paired off with 2 other points/nodes. Then there are only two possible shapes that these nodes can take that satisfy these conditions: 2 rings/circles of 3 points/nodes each, or 1 ring/circle of 6 points/nodes. Now consider each of those shapes in turn:

• 2 rings/circles of 3 points/nodes: You need to select 3 out of 6 points/nodes for the first ring/circle. Then, since there are two rings/circles and order doesn't matter, you need to divide by the possible number of ways to order those 2 rings/circles: ${\frac {\binom {6}{3}}{2!}}={\frac {20}{2}}=10$

• 1 ring/circle of 6 points/nodes: The general formula for a ring permutation is (n - 1)! / 2 = 5! / 2 = 60. (To see why the formula is thus, consider that after choosing any arbitrary node in the ring as your starting point, you have 5 nodes left to order, so 5!, but then you have to account for the shape being a circle and looping back to the beginning, so you have to divide by 2 since clockwise and counterclockwise orderings are equivalent upon reflection.)

10 + 60 = 70, and there's your answer.

—SeekingAnswers (reply) 22:31, 21 September 2012 (UTC)

Nice!65.128.190.136 (talk) 23:06, 21 September 2012 (UTC)

P.S. The problem is equivalent to asking for the number of undirected 2-regular graphs given n labeled nodes (sequence A001205 in the OEIS), where in this case n = 6. Also, the number of partitions of n into parts of size at least 3 (sequence A008483 in the OEIS) is useful in the calculations for determining how many shapes you need to consider. —SeekingAnswers (reply) 04:28, 22 September 2012 (UTC)

nPr?

How do I calculate nPr by hand? Let say in Ti 89 calculator, I type in nPr(9 , 2) = 72. So how can I do it without the calculator? Thanks!65.128.190.136 (talk) 23:06, 21 September 2012 (UTC)

${\frac {n!}{(n-r)!}}$, or $\prod _{i=n-r+1}^{n}i$ or $\prod _{i=1}^{r}(n-i+1)$. Widener (talk) 23:23, 21 September 2012 (UTC)

Or in simpler terms: P(15,4)=15*14*13*12, just multiply, first number is where you start with, second one is the number of factors to use. P(12,3)= 12*11*10 you get the idea. Ssscienccce (talk) 01:41, 22 September 2012 (UTC)

Wasn't this discussed on NPR ? :-) StuRat (talk) 01:44, 22 September 2012 (UTC)

Facepalm... all right, I laughed a little. --Kinu ^t/_c 04:36, 22 September 2012 (UTC)

September 22

a?

problem 20. I saw the answer key but still unable to understand what is going on. I understand the binary expansion part. I get lost in the statement "it follows that the coefficient of x^2012 is equal to 2^0 + 2^1 + 2^5 = 2^6. answer key part 1, answer key part 2. Thanks!Pendragon5 (talk) 00:02, 22 September 2012 (UTC)

A product of sums is the sum of all the possible products; say (a+b)*(c+d)*(e+f): the result will contain every product you can make by picking one of each sum,so for example a*d*e, b*c*e, b*c*f and five others.

In your polynomial, you know which factors supply the power of x part, so the rest must provide the coefficient: showing only the parts that make up the x²⁰¹² term : (x¹⁰²⁴+..)*(x⁵¹²+..)*(x²⁵⁶+..)*(x¹²⁸+..)*(x⁶⁴+..)*(..+ 32)*(x¹⁶+..)*(x⁸+..)*(x⁴+..)*(..+2)*(..+1). And 1*2*32=64=2⁶ Ssscienccce (talk) 02:11, 22 September 2012 (UTC)

Oh okay I think I got it now. Thanks! I also have another question. How can I convert 2012 into binary number without the answer key?Pendragon5 (talk) 19:37, 22 September 2012 (UTC)

Binary_numeral_system#Conversion_to_and_from_other_numeral_systems, first paragraph. — Quondum 21:02, 22 September 2012 (UTC)

For a number like 2012, close to 2048, (=2¹¹), a shorter way is: you know that 2¹¹-1 = 2047 is 11111111111, and 2047-2012=35; So you have to subtract 35 which is expressed as a sum of powers of two: 32 + 2 + 1, so from (32;16;8;4;2;1) you know the positions that have to become zeros to get 2012: 11111011100 Ssscienccce (talk) 08:56, 25 September 2012 (UTC)

Commutability of integration

Is $\int (\int f(r)dr)dv$ the same as $\int (\int f(r)dv)dr$? 71.207.151.227 (talk) 21:04, 22 September 2012 (UTC)

See Fubini's theorem. Sławomir Biały (talk) 21:09, 22 September 2012 (UTC)

September 23

Seeking function

Does anyone have any feeling whether any function f exists to satisfy the following:

$\int _{0}^{1}{\frac {x}{z^{2}}}f(x)f\left(x\left({\frac {1}{z}}-1\right)\right)\,dx=1$

for all 1/2 < z < 1

Of course, actual solution(s) would be even better, but failing that an idea of whether there are likely to be no solutions, one solution, or many solutions would be of interest. 81.159.105.97 (talk) 00:59, 23 September 2012 (UTC)

Intuitively I think there should be such a function. It should be easy (though computationally intensive) to find for every $\epsilon >0$ a function such that $\left|\int _{0}^{1}{\frac {x}{z^{2}}}f(x)f\left(x\left({\frac {1}{z}}-1\right)\right)\,dx-1\right|<\epsilon$, but in my experimentations the functions didn't seem to converge as $\epsilon \to 0$. -- Meni Rosenfeld (talk) 10:03, 24 September 2012 (UTC)

Thanks, could you outline the method you used to find that series of functions?

I tried writing f as a power series, and looking for coefficients such that, on evaluation of the integral, the z's from the f(x(1/z-1)) component cancelled out 1/z^2, based on the idea that z^2 = 1 - 2(1/z-1) + 3(1/z-1)^2 - 4(1/z-1)^3 + ... However, I could not get anything that looked solvable, or even looked as if it would converge as a power series. 86.128.6.76 (talk) 20:24, 24 September 2012 (UTC)

I wrote f as a polynomial of some degree, took a few evenly spaced values of z, and used a loss function based on the sum of squared difference between the actual and desired value of the integral on those points. I found the coefficients which minimize this loss. This requires the use of a CAS.

In fact I worked with $u=1/z$ rather than z. -- Meni Rosenfeld (talk) 09:46, 25 September 2012 (UTC)

Topology Norm on a space over a complex field

Is there any "recognized" metric [norm] which satisfies the Pythagorean Theorem even when the lengths of [vectors representing] sides in a triangle are not real [complex] numbers? (e.g. the hypotenuse will be 0 in [by] that metric norm if the lenghs of [vectors representing] the other sides are 1 and i; In other words: the length of the vector (1,i) will be zero, because 1² + i² = 0²). Additionally, can such a metric [norm] be regarded as Euclidean (or pseudo-Euclidean) in some sense? Or rather, can it even be regarded as the simple Euclidean metric [norm] on a space over the complex field? Is it a legitimate "recognized" metric [norm]? 77.126.50.25 (talk) 08:58, 23 September 2012 (UTC)

Would the pseudo-Euclidean Lorentz metric (Minkowski space) qualify? This still uses real numbers, but modifies signs in the Pythagorean theorem. The question is essentially circular, inasmuch as what is considered to be orthogonal (a "right angle") is defined by the metric (usually a symmetric bilinear form), including in any number of dimensions. Pure imaginary numbers can be used to produce the same effect. — Quondum 10:11, 23 September 2012 (UTC)

The circularity you've pointed at can be avoided by defining the space over the complex field (rather than over the real field), so that the two vectors (x,0) (0,y) be orthogonal - because their inner product is zero, yet x may equal 1 and y may equal i, in which case - the metric I'm looking for - determines the length of their sum (1,i) to be zero (because 1² + i² = 0²).

I suspect Minkowski space won't be sufficient, because of two reasons: First, it's not defined over the complex field - as opposed to what's expected from the space having the metric I'm looking for; Second, even if one realy tried to use Minkowski space over the complex field, its metric still doesn't fully obey the Pythagorean Theorem - but rather modifies signs - as you have already pointed out.

As long as I think about this, it seems that the metric I'm looking for is the simple Euclidean metric on a space over the complex field, isnt it? 77.126.50.25 (talk) 11:32, 23 September 2012 (UTC)

You are describing a space of two real dimmensions with a metric. If you choose to separately consider it as the complex field, this is irrelevant, since the complex multiplication is not used here except as you choose within the metric, and you are choosing to dismember it into it real and imaginary parts (i.e. two one-dimensional spaces over the real numbers) before defining the metric in terms of the pieces. You are separately defining (x,0) and (0,y) be orthogonal; you can't do this, it is determined by the metric (i.e. you have to find whether they are orthogonal under the metric you've defined). The metric you have described is exactly the Lorentz metric in two dimensions, where you have simply labelled the units on one axis with an "i". The two axes do turn out to be orthogonal, but vectors away from the axes behave a little counterintuitively, with those at 45° being self-orthogonal. This matches the behaviour of split-complex numbers rather than the normal complex numbers. If you were to try to define a "simple Euclidean metric" over the complex field in two dimensions, each "axis" would allow values from the whole field (you'd be dealing with 4 real dimensions). This construction works perfectly well, but I doubt that it is what you're looking for. — Quondum 13:00, 23 September 2012 (UTC)

Thanks to your comment, I've just fixed some mistakes in the old version of my original question, in order to make it clear that what I've been trying to describe - was not "a space of two real dimensions" - nor "two one-dimensional spaces over the real numbers", but rather one space of two complex dimensions. Btw, I didn't understand why I couldn't state that (x,0) and (0,y) are orthogonal; Doesn't this follow from the very definition of the orthogonality and the inner product? As to the name of the section, I've just changed it. 77.126.50.25 (talk) 14:14, 23 September 2012 (UTC)

The complex metric is "unrecognised" not because it is impossible to construct. It is "unrecognised" because fails to satisfy the triangle inequality, if not to mention that almost certainly evokes a lot of null vectors. And the existence of non-zero null vectors is a hint to impossibility of the Pythagorean Theorem in complex-valued "metric spaces" (which are actually not so by their core properties). BTW, I still do not realize why this section is named "Topology". Incnis Mrsi (talk) 13:28, 23 September 2012 (UTC)

As Quondum has indicated, physicists typically may not require the triangle inequality of a "metric" (although mathematicians typically do). 77.126.50.25 (talk) 14:38, 23 September 2012 (UTC)

For this I implicity assumed a definition of "metric" as quadratic form. Mathematicians typically require the triangle inequality of a "metric", whereas physicists don't. And in physics, the Lorentz "metric" is most certainly recognized and is used extensively. and yes, the section is misnamed, care to suggest another? — Quondum 14:08, 23 September 2012 (UTC)

See my response to your previous comment. 77.126.50.25 (talk) 14:15, 23 September 2012 (UTC)

Let's take a step back, and try to determine what you are looking for.

• We could define a quadratic form on an n-dimensional complex vector space. This will assign a complex value to each vector in this space. It could look mathematically very similar to the classical sum-of-squares in geometry, only with complex values (or the dot product on complexified vectors). It is full of null vectors, but that never bothered relativists. Regarded as a real vector space, it has a signature of (n,n).
• Alternatively, we can define a sesquilinear form (or else its associated "quadratic" form) on the same space. This will assign a real number to each vector. The end result is rather like (actually indistinguishable from) a 2n-dimensional (real) Euclidean space, with a signature of (2n,0).

I would assume from your description that the first is what you mean. There's nothing particularly recognized or not about it; it would be known as "an n-dimensional complex vector space with a nondegenerate quadratic form", or, if you're referring to the "metric" itself, "a nondegenerate quadratic form on an n-dimensional complex vector space". It trivially satisfies the Pythagorean identity for the addition of orthogonal vectors. — Quondum 15:15, 23 September 2012 (UTC)

Thank you very much, both for the information you presented - and for your patience; Yes, it seems like the first option is what I'm looking for (since the "magnitude"-function I'm looking for is supposed to assign a complex number, which - of course - may not be real). However, something still bothers me: I'm looking for a "magnitude"-function - being identical to the well celebrated Euclidean formula for calculating the length of the hypotenuse: this formula is supposed to look like a square root of sum of squares, but that formula does not have a "quadratic form", but rather a form of "a square root of a quadratic form". So are you still sure the first option may point at the correct direction for satisfying my requirement? 77.126.50.25 (talk) 18:50, 23 September 2012 (UTC)

It unfortunately does not easily lend itself to square roots, but best stays in the "squares form" a² + b² = c². You could take the square root of a complex number, at the cost of getting a two-valued complex "norm". We have for complex vectors a and b that a⊥b (by definition) when a⋅b=0. The "magnitudes squared" are a²=a⋅a and b²=b⋅b. We have then that (a+b)²=(a+b)⋅(a+b)=a²+b²+2a⋅b=a²+b². All in complex numbers. Then you can take the two-valued square root if you wish, still complex. It seems to fit, unless you wish to restrict this last to positive reals. You can get this last restriction with the sesquilinear form, but this involves all sorts of conjugates, so no true squaring in the Pythagorean expression. With more context on what is needed it could be easier to determine what you want. — Quondum 21:30, 23 September 2012 (UTC)

Thanks. Two points to be clarified:

1. You wrote in your previous response: "an n-dimensional complex vector space with a nondegenerate quadratic form...It trivially satisfies the Pythagorean identity for the addition of orthogonal vectors". Does every (nondegenerate) quadratic form (on a complex vector space) really satisfy the Pythagorean identity (for the addition of orthogonal vectors)? Aren't there (nondegenerate) quadratic forms (on a complex vector space) other than the form a² + b² = c²? I'm asking about that, because I'd like to be sure that - the verbal expression you used - really refers uniquley to what I'm looking for, that is: a legitimate/standard/known (verbal) expression/term/name, for all complex vector spaces - which have a "magnitude"-function satisfying the Pythagorean identity.

2. Why didn't mathematicians define the Euclidean space also over the complex field? Note that if they did, then the original Euclidean definition of the norm (on a real vector space) $\|\mathbf {x} \|={\sqrt {\mathbf {x} \cdot \mathbf {x} }}$ could still hold - even when one replaces the (original) real vector space by a complex vector space, except that the mathematicians wouldn't use the name "norm" (since the Euclidean definition of the norm doesn't satisfy the triangle inequality when the field is complex) but rather a similar name, e.g. "Pseudo-norm", or "length", or "magnitude", and likewise. Additionally, phisicists could apparently use the term "Euclidean space over a complex field" - without changing anything (even not the name "norm"), because they don't really care about the triangle inequality (as you've already pointed out), correct? 77.126.50.25 (talk) 12:04, 24 September 2012 (UTC)

a² + b² = c² is the addition formula relating the squares of orthogonal vectors being added; the quadratic form is $q(\mathbf {x} )=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}x_{i}x_{j},\mathbf {x} =(x_{1},...,x_{n})$, which is what assigns a complex number to each vector with the given complex components. Every non-degenerate quadratic form over complex vectors is equivalent: you can always diagonalize it to the form $q(\mathbf {x} )=\sum _{i=1}^{n}{x_{i}}^{2}$ by suitably choosing your basis (essentially the axes and their scaling). So, yes: for any given dimensionality, there is really only one "complex vector space with a non-degenerate quadratic form".

On your second point, you could define an ℝ-linear "norm" $\|\mathbf {x} \|={\sqrt {|q(\mathbf {x} )|}}={\sqrt {|\mathbf {x} \cdot \mathbf {x} |}}$, which might be useful in scaling, e.g. $\mathbf {x} /\|\mathbf {x} \|$ to get a "unit" vector. Alternatively, as I've said before, a ℂ-linear "norm" $\|\mathbf {x} \|={\sqrt {q(\mathbf {x} )}}=\pm {\sqrt {\mathbf {x} \cdot \mathbf {x} }}$ (with true ambiguity on the sign due to the square root of a complex number), for a similar purpose. The rest is simply a debate about naming, which is a problematic area. — Quondum 14:55, 24 September 2012 (UTC)

I feel I'm approaching (slowly) to my target, but unfortunately I haven't reached it yet. Let's put it clearer: My target is to reach a legitimate verbal expression denoting a (quadratic) space (over a complex field), with the ℂ-linear "norm" $\|\mathbf {x} \|$ satisfying: $\|\mathbf {x} \|^{2}=\mathbf {x} \cdot \mathbf {x}$. However, if I don't define the "norm" in advance, then how can I derive the ℂ-linear "norm" $\|\mathbf {x} \|^{2}=\mathbf {x} \cdot \mathbf {x}$ from the very fact that the space has a (nondegenerate) quadratic form $q(x)=a_{1}x_{1}^{2}+a_{2}x_{2}^{2}$??? Btw, if one really defines the "norm" as the ℂ-linear "norm" $\|\mathbf {x} \|$ satisfying: $\|\mathbf {x} \|^{2}=\mathbf {x} \cdot \mathbf {x}$, then one no longer needs the information telling us that the space has a quadratic form, does one? 77.126.50.25 (talk) 17:51, 24 September 2012 (UTC)

You need to define only one of the following, the other two follow naturally ("are induced") [ with derivations ]:

• A quadratic form q(x) [ = B(x,x) = ||x||² ]
• A symmetric bilinear form B(x,y) (also known as a scalar product, written x⋅y) [ = (q(x+y) − q(x) − q(y))/2 ]
• A ℂ-linear "norm", which we could (somewhat unconventionally) write ||x|| [ = ±(q(x))^1/2 ]

Most of this is in the linked articles. It is usually cleanest to start with one of the first two. The original wording I gave you suffices; anything further would amount to stating that or showing how the remaining aspects (uniqueness up to isomorphism, dot product, "norm") follow naturally from the description. — Quondum 19:17, 24 September 2012 (UTC)

I didn't quite answer "from the very fact that...". This is a little more involved, but not too complicated. It is essentially all in Quadratic form, though it is not all that clear that the equivalence is rooted in a suitable change of basis, and that complex vector spaces have exactly one case for non-degenerate quadratic forms, unlike real vector spaces, which have n+1 cases. — Quondum 19:43, 24 September 2012 (UTC)

1. Is it really natural/conventional/common/standard to regard the quadratic form as a magnitude/norm/length?

2. Why did you write "norm" with quotation marks? Was that just because this "norm" isn't really a norm - because it doesn't satisfy the triangle inequality when the field is complex?

3. You write: "You need to define only one of the following...The original wording I gave you suffices; anything further would amount to stating that...the remaining aspects...follow naturally...". Naturally, i.e. not logically/mathematically - unless you define (some of) them in advance, i.e. one could talk about a "complex vector space with a nondegenerate quadratic form", but with an (unnatural) "norm" $\|\mathbf {x} \|$ other than: $\mathbf {x} \cdot \mathbf {x}$, couldn't one?

4. Btw, how about the shorter expression "nondegenerately-quadratic space over a complex field"? 77.126.50.25 (talk) 20:54, 24 September 2012 (UTC)

1. I'm not trained in the area (especially terminology); terminology can be dizzyingly confusing. All of these would be unconventional.
2. I expect you to have problems finding a simple accepted term for the square-root-of-the-quadratic-form. Hence my quotation marks.
3. You can define any structure you like, as long as it's mathematically consistent. You could even (re)define your terminology. You could define twenty different simultaneous scalar products; it's just that when the structures are directly related (induced by each other), they are more natural, as when a particular construction leads to a related structure in a unique way (e.g. up to an isomorphism). If one needs to make an arbitrary choice, it's unnatural (or that's how I interpret this not-too-well-defined term). So "n-dimensional complex vector space with a nondegenerate quadratic form" is pretty unambiguous; if you then refer to the "naturally induced scalar product", and the "cannonical quadratic form", you'll probably be understood. I'd then perhaps use the suggestive term such as "complex magnitude" for its bivalued square root, introduced with clarification.
4. Maybe "nondegenerate quadratic complex space"? Depending on context, you could introduce the term with a more comprehensive definition to clarify exactly what you mean, possibly further shortening it (e.g. drop the "nondegenerate") if you wish. What you would want to call the length-substitute I have no idea. Judging by the length of this thread, you may get more attention from the real mathematicians by starting a new section simply for vetting a proposal on terminology. — Quondum 03:04, 25 September 2012 (UTC)

Ok, here is how I see it now, thanks to your comments: the expression "n-dimensional complex vector space with a non-degenerate quadratic form" - suffices to describe what I'm looking for, because such a space naturally induces a (complex) magnitude being the canonical quadratic form - what really makes the space satisfy the Pythagorean identity (= what I need).

I preferred to say "nondegenerately-quadratic space over a complex field", because if I said "nondegenerate quadratic complex space" then it would mean that the space itself is not degenerate, i.e. that it contains more than the zero-vector, whereas by "non-degenerately" I refer - not to the space itself - but rather to its being quadratic. Anyways, "nondegenerately quadratic complex space" is really shorter. 77.126.50.25 (talk) 09:23, 25 September 2012 (UTC)

I don't agree with "a (complex) magnitude being the canonical quadratic form - what really makes the space satisfy the Pythagorean identity". What I call the complex magnitude squares to the quadratic form, so it is not the same thing. And don't confuse the cannonical quadratic form with the Pythagorean identity (though it does make seeing its relation to scaled basis vectors simpler): it does not have to be in any particular form for this identity to hold: the sum of the squares of the complex magnitudes of any set of mutually orthogonal vectors equals the square of the complex magnitude of the sum of the vectors. — Quondum 10:29, 25 September 2012 (UTC)

You could say: "... such a space naturally induces a (complex) magnitude and orthogonality condition that satisfy the Pythagorean identity". (The orthogonality condition is, of course, x⋅y=0, the dot being the naturally induced scalar product) Simpler, no? — Quondum 10:59, 25 September 2012 (UTC)

Cantor set and compactness

The article on the Cantor set says that every compact metric space is the continuous image of the Cantor set. If I do not misunderstand it means that for every compact space X there is a continuous onto function with domain the Cantor set and range X. But won't the cardinality of X be at most the continuum as if f is an onto function from A to B then |B|<=|A|? What if X has cardinality more then the continuum?-Shahab (talk) 15:42, 23 September 2012 (UTC)

We can show that there are no compact metric spaces with cardinality larger than the continuum. (This is off the top of my head, so I apologize if it is ugly:-)) First, we show that any second countable metric space has cardinality no larger than the continuum, then we show that every compact metric space is second countable. Let X be a second countable metric space and D a countable dense subset. Since X is hausdorff, x is in the closure of D iff there is a sequence in D limiting to x; thus, since the closure of D is X, there is an onto map from sequences in D that have a limit in X and points in X. There are at most continuum many such sequences, thus X cannot have cardinality larger than the continuum. Now, let Y be compact metric, we show Y is second countable. Let U(n) be the set of all open balls of radius 1/n; clearly, U(n) is a cover of Y, so a finite subcover F(n) exists. Pick a center for each ball in F(n) and call this set C(n), we'll show that the union C of all the C(n) is dense (it's obviously countable). Let y be any point in Y, since y is in some ball in F(n) there is a point y(n) in C(n) that is no further than 1/n from y; clearly, y(n) limits to y, thus, C is dense.Phoenixia1177 (talk) 19:57, 23 September 2012 (UTC)

Number of partitions

How does it come that math packages (for example, sagemath) can calculate the number of partitions in less than a sec? And that's apply even to numbers like 34349834 or like that. How is it so effective?Ptg93 (talk) 22:54, 23 September 2012 (UTC)

Modern computers can literally make billions of calculations per second, and sufficiently fast approximation formulas for the partition function are known, and indeed are discussed in the very article you linked to in your question, "partition (number theory)". —SeekingAnswers (reply) 05:58, 24 September 2012 (UTC)

Hard graft by programmers also counts. Even something like multiplication can involve involve implementing lots of complicated algorithms like the Schönhage–Strassen algorithm. Dmcq (talk) 08:35, 24 September 2012 (UTC)

I didn't find a satisfactory answer in the article. I don't know about Sage, but Mathematica can find the number of partitions of $10^{8}$ in 4 seconds, exactly apparently. The approximations are approximations, and the exact methods described seem to scale quadratically, meaning $10^{8}$ would take weeks even with billions of calculations per second.

So what algorithm is used? What is its runtime complexity? -- Meni Rosenfeld (talk) 09:59, 24 September 2012 (UTC)

There is a good description of what's done at Sage Days 35: Algorithms in Number Theory and FLINT - Fast Special Functions which describes the process with lots of detail. That is for Sage but Mathematica is basically the same on this. It isn't straightforward even with a fast machine to get it done so quickly. Dmcq (talk) 11:42, 24 September 2012 (UTC)

Hm, I was going to look at Mathematica's implementation notes after playing around a bit, but then it slipped my mind. For reference, it says "PartitionsP[n] uses Euler's pentagonal formula for small n and the non-recursive Hardy-Ramanujan-Rademacher method for larger n."

Fredrick Johansson, didn't he use to hang out around here? -- Meni Rosenfeld (talk) 12:49, 24 September 2012 (UTC)

Just for reference for those who would like more context/information:

• Euler's pentagonal formula is discussed in detail in the article "pentagonal number theorem", and I just added a note about it to the "partition (number theory)" article, which previously lacked any mention of the formula.
• The Hardy-Ramanujan-Rademacher method is discussed in the article "partition (number theory)".
• Fredrik Johansson (not Fredrick Johansson) is one of the programmers of Sage.

—SeekingAnswers (reply) 19:25, 24 September 2012 (UTC)

Probably User:Fredrik, but it seems they abandoned the place two years ago unfortunately. Dmcq (talk) 13:34, 24 September 2012 (UTC)

The code for Sage is at [1] and the original author is given as Jonathan Bober. Who would have thought the best way to compute it would involve pi, sqrt, sin, cos, cosh and sinh? Dmcq (talk) 14:41, 24 September 2012 (UTC)

September 24

something in Pythagoras tree (fractal)

In Pythagoras tree (fractal) there is "box of size 6L × 4L>." Does the ">" mean anything or is it a typo? (There is another one later.) Bubba73 ^{You talkin' to me?} 01:55, 24 September 2012 (UTC)

Just a typo. It was accidentally introduced when a reference was added: see [2]. —Bkell (talk) 02:22, 24 September 2012 (UTC)

Resolved

Bubba73 ^{You talkin' to me?} 03:22, 24 September 2012 (UTC)

Parity of elements of a pythagorean triple

Hello.

I'm having trouble with arriving to a proof that, if a, b and c are pythagorean triples without a common factor (a = p² - q², b = 2pq and c = p² + q²) then exactly one of a, b must be even and the other odd.

Any help is appreciated.186.28.123.46 (talk) 16:04, 24 September 2012 (UTC)

Clearly b = 2pq is even. If a is also even, what is the parity of c² ? So what is the parity of c ? So what factor do a, b and c have in common ? Gandalf61 (talk) 16:12, 24 September 2012 (UTC)

If both a,b are odd, then a²,b² have a remainder of 1 when divided by 4, and so a²+b²=c² has a remainder of 2 when divided by 4, but it is impossible for a square number. Therefore, at least one of a,b is even. --84.229.150.202 (talk) 18:48, 24 September 2012 (UTC)

September 25

a thousand coins a thousand times?

This is not a homework question, and it's probably a little frivolous, so if you don't like it don't answer. But I'm curious, how would you go about solving this problem: Toss a thosand coins a thousand times, on average, what is the longest streak of either heads or tails? If it's not clear, you toss one coin a thousand times, in that sequence you get a streak of 13 heads. Repeat that a thousand times and take the average of the longest streaks. I could maybe get a decent answer if I wrote a program, but it would take a few hours for me to work it out. Is there a mathy way to do this with a few equations? Vespine (talk)

A sequence of identical outcomes is known as a run. This page from Wolfram Mathworld reviews the methods that are needed to answer your question. The simplest way to get an answer is to use formula 15 from that page, imagining that all of your trials are concatenated together, so that the whole experiment is reduced to a sequence of a million coin tosses. Plugging into the formula gives an answer of about 13.1. That will be a little bit of an overestimate, because it includes runs that cross trial boundaries, but for runs of this length those will only be about 1% of the total. Looie496 (talk) 05:19, 25 September 2012 (UTC)

I ran a simulation with a million trials of 1000 flips each, and got 10.3 for the average length of the longest run of either heads or tails in each trial. If you only allow heads runs or only allow tails runs, then it drops to 9.3. This information is only intended as a check against the formula answer given above. StuRat (talk) 06:05, 25 September 2012 (UTC)

A pseudo-random generator would not be suited for this kind of simulations I think. They won't generate all possible sequences.

Looie496: You seem to have used the natural logarithm; it should be the logaritm base 1/p = 2 giving 18.9 Ssscienccce (talk) 06:21, 25 September 2012 (UTC)

A way to show that 13.1 would likely be too low is: assume trials of 15 throws: on average 1 out of 32768 would give all 15 heads. Thats for a total of 491520 throws; so a million throws would on average give two runs of 15 heads, and that's without counting the more frequent runs crossing boundaries. Ssscienccce (talk) 06:58, 25 September 2012 (UTC)

How do you get 491520 throws ? And how did you get 2 out of a million from that ? As for the average longest run being 18.9, that seems way too high. The chances of getting exactly 19 heads in a row, are, by my calculations: (1001-19)/(0.5)¹⁹ = 982/524288 = 0.00187, or 0.00374 for either a run of heads or tails. That's just too unlikely to be the average run length. StuRat (talk) 08:19, 25 September 2012 (UTC)

Yep, mistake, I was responding to what I assume Looie was talking about, based on the formula he mentioned and the result he got. As far as I can tell, the only way to get 13.1 would be ln(1000000*(1-0.5)) Ssscienccce (talk) 09:02, 25 September 2012 (UTC)

I see. What do you get when you plug in 1000 flips instead of a million ? (I don't know how to do log₂(500) on my calculator.) StuRat (talk) 09:13, 25 September 2012 (UTC)

That gives 8.96 for a specific outcome (head or tails), 9.96 if it doesn't matter. You can calculate the log_b(x) with log(x)/log(b) or ln(x)/ln(b) Ssscienccce (talk) 10:19, 25 September 2012 (UTC)

I agree with StuRat, it's 10.4 in my simulation. For the 1000 trials, the longest runs are 7 in sequence (17 times), 8 (104), 9 (237), 10 (245), 11 (137), 12 (95), 13 (62), 14 (35), 15 (16), 16 (9), 17 (2), 18 (3), 19 (1), 20 (1). Dragons flight (talk) 08:01, 25 September 2012 (UTC)

When I try to do it mathematically, from scratch, I get approximately 13, as well:

Let's just look at the case of getting 13 heads in a row. To do that out of 13 throws would be a 1/2¹³ probability, or 1/8192. Now, the number of positions where you could possibly get a run of 13 is 1001-13 or 988. So, the probability of 13 heads appearing anywhere within the 1000 flips is approximately 988/8192, or 0.1206. If we consider the possibility of either 13 heads or tails in a row, then we double the probability to 0.2412. So, you then need to repeat these calculations for every possible run length, from 1 to 1000, then combine this info together to figure out the average run. Using the above method as a reasonable approximation, I wrote a program to do the math for me (no simulation, just crunching formulas). So, I took the probability of having a 1000 coin run, added that to the probability of a 999 coin run, etc., until I got to a 50% chance. I get a result of about 13.

So, we have an odd discrepancy between 13.0-13.1 in theory and 10.3-10.4 in simulations (and Ssscienccce's answer of 18.9 seems way high). I suspect the difference is due to the handling of multiple runs of the same length (the math is counting these multiple times, when it should only count them once). I believe the experimental result to be the correct one. StuRat (talk) 05:39, 25 September 2012 (UTC)

I think Ssscienccce is calculating the expected value of the longest run in a sequence of 1,000,000 trials. However, what Vespine is asking for is the expected value of the average of the longest run in a set of 1,000 sequences of 1,000 trials each. By the law of large numbers, this will be close to the expected value of the longest run in a single sequence of 1,000 trials. Gandalf61 (talk) 08:28, 25 September 2012 (UTC)

Yep, that's what I thought Looie was talking about. (Seems that random number generators are better than I assumed btw.) Ssscienccce (talk) 08:32, 25 September 2012 (UTC)

StuRat's simulation seems to deal with tossing 1 coin 1000 times. The OP asked about tossing 1000 coins 1000 times and taking the max, which is higher.

I ran 20 trials with 1000 coins and got an average of 20.25 and stdev 1.5, meaning the true mean is likely to be between 19.5 and 21. -- Meni Rosenfeld (talk) 09:41, 25 September 2012 (UTC)

His clarification was "you toss one coin a thousand times, in that sequence you get a streak of 13 heads. Repeat that a thousand times and take the average of the longest streaks." That seems to support my interpretation. StuRat (talk) 09:47, 25 September 2012 (UTC)

Sorry, I see that now and you beat me to deleting my comment. -- Meni Rosenfeld (talk) 09:50, 25 September 2012 (UTC)

Let me explain in more detail what I think is at the root of the discrepancy between my mathematical answer (which I think is wrong) and my experimental simulation answer (which I think is right). Consider a simplified problem where we toss a coin 4 times and want to know the probability of getting either 3 heads in a row or 3 tails in a row. Let's list every possible combo and mark those with 3 in a row with a star:

HHHH *
HHHT *
HHTH
HHTT
HTHH
HTHT
HTTH
HTTT *
THHH *
THHT
THTH
THTT
TTHH
TTHT
TTTH *
TTTT *

So, we have 6/16 cases which match our goal, giving us a 3/8 probability. Now let me use the same math I used previously. The chance of flipping 3 in a row heads out of 3 is 1/8. The chances of flipping 3 in a row either heads or tails out of 3 is 1/4. There are two ways to get 3 in row, either the first 3 of 4 flips, or the last 3 of 4 flips. So, multiply that 1/4 probability by 2 and we get a 1/2 probability. Therefore, the math predicts a higher probability than it should. I believe the reason for this is that the first and last cases listed above each have 2 series of 3 in a row, overlapping. So, instead of 6/16 cases, we get 8/16 cases.

Now let's look at the longest run in each case above:

HHHH 4
HHHT 3
HHTH 2
HHTT 2
HTHH 2
HTHT 1
HTTH 2
HTTT 3
THHH 3
THHT 2
THTH 1
THTT 2
TTHH 2
TTHT 2
TTTH 3
TTTT 4

The average length of a run is therefore 2.375. I don't see how you get that from the formula R = log_(1/p)[n(1-p)] listed in the Wolfram Mathworld link. So, either I don't understand how to use the formula, it's incorrect, or should not be applied to this problem. StuRat (talk) 10:25, 25 September 2012 (UTC)

The formula gives the longest run most likely to get, but to calculate the average of the longest runs, I don't see an obvious way... Ssscienccce (talk) 11:48, 25 September 2012 (UTC)

What do you mean by "longest run most likely to get"? The expected longest run (~ average of longest runs over many trials) will be a rational number, whereas that Mathworld formula in general yields an irrational number, so it either means something else (don't know what) or it is incorrect. 86.176.214.152 (talk) 12:52, 25 September 2012 (UTC)

Error in published paper?

According to page 314 of

Garza, G.; Young, J. (2004), "Wieferich Primes and Period Lengths for the Expansions of Fractions", Math. Mag., 77 (4): 314–319, doi:10.2307/3219294,

the period p of a number x in base b is the smallest number p such that b^p ≡ 1 (mod x). If x is a prime number satisfying b^x−1 ≡ 1 (mod x²), then x is called a Wieferich prime in base b. They claim at the beginning of the paper that the period of x = 1093 (the first base 2 Wieferich prime) is 1092 and that this is also the period of x². However, I do not understand how this fits with the result of W. Meissner, who in

Meissner, W. (1913), "Über die Teilbarkeit von 2^p − 2 durch das Quadrat der Primzahl p=1093", Sitzungsber. D. Königl. Preuss. Akad. D. Wiss. (in German), Zweiter Halbband. Juli bis Dezember, Berlin: 663–667

shows that 2³⁶⁴ ≡ 1 (mod 1093²). So why is the period of 1093 1092 and not 364? -- Toshio Yamaguchi (tlk−ctb) 10:28, 25 September 2012 (UTC)

To clarify, the term period here refers to the period of the expansion of ${\tfrac {1}{x}}$. -- Toshio Yamaguchi (tlk−ctb) 10:45, 25 September 2012 (UTC)

vectors and matrices

given a vector v_i i∈[1,N] is there an algebraic operation that yields the matrix diag[v₁, v₂ ... v_N ]? — Preceding unsigned comment added by 92.11.64.50 (talk) 12:35, 25 September 2012 (UTC)

Does Σ_i e_i e_i^T v e_i^T work? — Preceding unsigned comment added by 92.11.64.50 (talk) 12:47, 25 September 2012 (UTC)