Math: Fleeting Thoughts

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Eastwinn
Posts: 303
Joined: Thu Jun 19, 2008 12:36 am UTC
Location: Maryland

Re: Math: Fleeting Thoughts

Postby Eastwinn » Tue Aug 31, 2010 9:33 pm UTC

letterX wrote:Stirling's approximation: know it!


Yesssssss. Perfect. :D
http://aselliedraws.tumblr.com/ - surreal sketches and characters.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Math: Fleeting Thoughts

Postby Macbi » Tue Sep 28, 2010 10:01 am UTC

How many essentially different game theoretic scenarios are there with 2 players, each choosing between 2 options?
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Math: Fleeting Thoughts

Postby Talith » Tue Sep 28, 2010 5:34 pm UTC

By different game types do you mean eg. prisoner's dilemma, stag hunt, chicken, 1 player domination etc?

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: Math: Fleeting Thoughts

Postby Quaternia » Tue Sep 28, 2010 10:28 pm UTC

Macbi wrote:How many essentially different game theoretic scenarios are there with 2 players, each choosing between 2 options?

What do you mean by "essentially different"?

Because you can have infinitely many game setups with 2 players and 2 options (make one, then for the second multiply each entry by 2, etc.) but the outcome remains the same. There's also the case where you have imperfect information and a coefficient of loss of information or something, and you can assign any positive real number up to 100 to that, etc..

If you want to know how many different setups there can be where one player beats another or ties them on a case, you can calculate that (it's finite) if I am not mistaken. This reduces to: "you've got 4 cases, each case can have 3 different options, how many different setups can you have".

If you want to know how many different possible game rules/setup there are (and if that's finite), then... well, I would say infinite (?), because it's as far as imagination takes you... Then again, I guess that after a while, you'd start having some patterns between games...
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Math: Fleeting Thoughts

Postby Talith » Tue Sep 28, 2010 10:49 pm UTC

There are a few different ways of analysing a 2 person game with 2 options. You might want to ask the question; How many different ways can a Nash equilibrium be distributed about a payoff matrix. I suppose that is basically the same as asking the question; how many different ways can I colour in 4 boxes with 1 colour? The answer to which is 2^4=16 (unless you count a game with opposite NEs the same, ie does the NE '1A 2B' equal the NE '1B 2A' - also I'm not sure if having no NE is the same as having all 4 choice combinations being an equilrium). But then NEs can be stable and unstable. If you have more than one NE then one might be risk dominant while the other is payoff dominant. Repeated games add another twist. There are a lot of other ways in how game types can differ. Unless you give a specific definition of 'essential different game theoretic scenarios' we can't really go much further.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: Math: Fleeting Thoughts

Postby Quaternia » Tue Oct 05, 2010 12:59 am UTC

*BUMP* because I think I have a general answer to the OP's question.
Consider the following two person logic game.
[imath]\forall x \exists y P(x,y)[/imath]
Where [imath]x \in[/imath] {a,b} and [imath]y \in[/imath] {c,d}.
Player 1 picks the x, Player 2 picks the y. Player 1 wins if the Decidable Property P is false, Player 2 wins if the property P is true.
This is a two-player, two-option game, as Player 1 can only choose either a or b, and Player 2 can only choose either c or d. (Xor, the or is exclusive)
There are as many games of this type as there are decidable properties that involve some sort of relation between two objects in the logic used! (in a not-too-weird logic that has quantifiers as well as some other concepts that I used implicitely)


-----Old Post below, edited------
Plus if we're considering all 2-person 2-option games, then there's a large variety of non-zero-sum games, which adds yet another level of "different game types".
And then there's special types of games where players distrust each others' rationality, where you have a coefficient for expected rationality of the other player, and you have to take that into account, etc.
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Math: Fleeting Thoughts

Postby You, sir, name? » Tue Oct 05, 2010 4:09 pm UTC

FT:
[math]\log \prod_i k_i = \sum_i \log k_i[/math]
I wouldn't accuse it of being particularly useful, but the identity is pretty to look at.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Math: Fleeting Thoughts

Postby letterX » Tue Oct 05, 2010 5:05 pm UTC

... you... wouldn't call that useful? It's pretty much the reason we have logarithms.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Math: Fleeting Thoughts

Postby You, sir, name? » Tue Oct 05, 2010 5:18 pm UTC

letterX wrote:... you... wouldn't call that useful? It's pretty much the reason we have logarithms.


Well, it's an important property, but hardly stuff you rely on in your day-to-day calculations (at least not in this general form).
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Math: Fleeting Thoughts

Postby Syrin » Tue Oct 05, 2010 6:21 pm UTC

Quaternia wrote:Consider the following two person logic game.
[imath]\forall x \exists y P(x,y)[/imath]
Where [imath]x \in[/imath] {a,b} and [imath]y \in[/imath] {c,d}.
Player 1 picks the x, Player 2 picks the y. Player 1 wins if the Decidable Property P is false, Player 2 wins if the property P is true.
This is a two-player, two-option game, as Player 1 can only choose either a or b, and Player 2 can only choose either c or d. (Xor, the or is exclusive)
There are as many games of this type as there are decidable properties that involve some sort of relation between two objects in the logic used! (in a not-too-weird logic that has quantifiers as well as some other concepts that I used implicitely)


If you remove the [imath]\forall x \exists y P(x,y)[/imath] statement, then there are only 24 games of this type.

User avatar
Eebster the Great
Posts: 3103
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Math: Fleeting Thoughts

Postby Eebster the Great » Wed Oct 06, 2010 12:16 am UTC

I think pretty much the reason we have logarithms is
1. inverse exponential
2. integral of 1/x
3. multiply-add

The third is becoming much less significant as time goes on.

User avatar
Dason
Posts: 1310
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Math: Fleeting Thoughts

Postby Dason » Fri Oct 08, 2010 5:34 am UTC

Eebster the Great wrote:I think pretty much the reason we have logarithms is
1. inverse exponential
2. integral of 1/x
3. multiply-add

The third is becoming much less significant as time goes on.

I dunno. The third is still very significant to me. If only because when I find maximum likelihood estimates it's typically A LOT easier to find the maximum of the log of the likelihood than it is the likelihood itself which is entirely due to the third property you have there.
double epsilon = -.0000001;

User avatar
phlip
Restorer of Worlds
Posts: 7556
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Math: Fleeting Thoughts

Postby phlip » Fri Oct 08, 2010 6:01 am UTC

Log scales are still useful, and use that property... adding a certain distance on the scale is equivalent to multiplying the value the position represents by a certain value.

Just 'cause I haven't used a slide rule in several weeks doesn't mean that log scales are now useless...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Math: Fleeting Thoughts

Postby You, sir, name? » Thu Oct 14, 2010 8:00 pm UTC

Ok, I'm kinda tired at the moment, but tell me if I'm making sense now. I want calculate an expression like this

[math]\frac{\partial}{\partial t} \int_{-\infty}^{t} ds F(s,t)[/math]

So I re-wrote it as

[math]\frac{\partial}{\partial t}\int_{-\infty}^{\infty} ds F(s,t)H(t-s)[/math]

Where H is the Heaviside step function. So now

[math]\frac{\partial}{\partial t} \int_{-\infty}^{\infty} ds F(s,t)H(t-s) = \int_{-\infty}^{\infty} ds (\dot{F}(s,t)H(t-s) + F(s,t)\delta(t-s)) = F(t,t) + \int_{-\infty}^{t} ds \dot{F}(s,t)[/math]

Is this horrible and wrong, or am I doing it right?
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Math: Fleeting Thoughts

Postby jestingrabbit » Fri Nov 19, 2010 2:53 pm UTC

The word "proof" is a noun that denotes a series of propositions that establish some truth. The word "prove" is a verb that denotes the act of assembling a proof.

That is all.

Edit: inserted an "a".
Last edited by jestingrabbit on Fri Nov 19, 2010 3:09 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Eebster the Great
Posts: 3103
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Math: Fleeting Thoughts

Postby Eebster the Great » Fri Nov 19, 2010 3:00 pm UTC

jestingrabbit wrote:The word "proof" is a noun that denotes a series of propositions that establish some truth. The word "prove" is verb that denotes the act of assembling a proof.

That is all.

Oh yeah? Prove it.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Math: Fleeting Thoughts

Postby Talith » Sat Nov 20, 2010 12:13 am UTC

I've been going kind of mad recently with the awesomeness of flexagons and their non-planar flexahedron coutnerparts - I wish there was more reading material on them if I'm honest-. Anyway, I have a feeling that the tetra-hexaflexahedron is a 3d immersion of the real projective plane (when it's in the state where it appears to have no hole going through the centre, so I'm not particularly interested in its flexing properties, I'm just considering one of it's states and then identifying the 2-manifold that it represents). I mainly think this because of the following reasons, which might not be founded;

1) It has 18 triangular faces, 27 edges and 10 vertices so it has Euler characteristic 1.
2) If you think of the pinched lines as lines of self intersection, ie as places where you change your orientation (so you change your orientation when you pass from the northern hemisphere of one lobe to the southern hemisphere of another love, if that makes sense), then it's non-orientable.

The only problem is, it doesn't look much like the Boy surface, Roman surface or cross-cap. It kind of looks like the Roman surface except it has 3 'lobes' instead of 4.

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: Math: Fleeting Thoughts

Postby Kurushimi » Sat Nov 27, 2010 3:17 am UTC

I've been looking at discrete dynamical systems lately and been trying to figure out a way to tell which points are an attracting points, which are repelling, and which are neither. For example if you have [imath]x_0 = c[/imath], and [imath]x_{n+1} = x_n^2 - 4x_n + 6[/imath], where c can be any starting complex number. You first find fixed points by solving the equation [imath]x_n = x_{n+1}[/imath] which in the above case yields x = 2 and x = 3. Whenever you put a complex number c such that abs(c - 2) < 1 for [imath]x_0[/imath] the series of x's will converge to 2, so two is an attracting point (I'm not sure if these are actually proper terms, but that's how I refer to it). The series of c's only "converges" to 3 if you put in exactly 3 for c (in which case, all the [imath]x_n's[/imath] will be 3's), any other value, even those really close to three, just run away from 3, so 3 is a repeller (again, my terminology)/ There are points that are neither attractors nor repellers, for example if you have [imath]x_0 = c[/imath] and [imath]x_{n+1} = x_n^2[/imath] then choosing a point c anywhere on the unit circle centered at the origin will cause the series of x's to just rotate around the origin in the complex plane.

Anyways, I thought of a function that could determine if point was an attractor, a repeller or neither. Basically, given a function f(x) which generates the series of x's, ( that is[imath]x_{n+1} = f(x_n)[/imath]), after you've found a fixed point p (interpreted as a complex number), you look at a function g(x,p)
[imath]g(x,p) = |x-p|^2 - |f(x)-p|^2[/imath]

That is, the square of the absolute value of x minus the fixed point p minus the square of the absolute value f(x) minus the fixed point p. Since the absolute value is really just distance, this is the same as subtracting the distance a point x is from the fixed point before f(x) is applied to its distance after f(x) is applied. If this value is positive, x is getting closer to p. If this value is negative, x is getting further away. For a point to be an attractor, every point in some neighborhood around it must be getting closer, hence g(x,p) must be positive, greater than 0. Since at the point p itself, g(p,p) = 0, we can conclude that if p is an attractor, g must have a minimum at point p. Similar logic can be applied to show that g must have a maximum at p if p is a repeller. I recently learned in multivariable calculus class how to find if a point is a maximum and minima of two valued functions (in the case g, the values are the real and imaginary components of x, since p is really just a constant), by calculating the discriminant of the function at point p.

I want to see if I can use this to go find the radius of convergence for attracting points but I've been having trouble making attracting points at all. Most of the time all fixed points of functions I think up are either repelling or neither repelling or attracting.

User avatar
rat4000
r/ratsgonewild
Posts: 451
Joined: Mon Feb 09, 2009 7:51 pm UTC

Re: Math: Fleeting Thoughts

Postby rat4000 » Sat Mar 26, 2011 10:39 pm UTC

I know this is a necro, but hey, I liked the thread while it was going strong and this s a question with a three-line answer at most...

Say I have six six-sided, fair dice and roll them (all of them at once) twice. I win if at least two of the dice are sixes and don't make a second roll if I win on the first one. What's my probability of winning?

I first decided to figure out P(two sixes), that is, the probability that I get two sixes when I throw all the dice. This is a binomial distribution question because there is a fixed amount of distinct objects and there are two distinct possibilities for every object: either it is a six or it isn't. Now, the probability of winning would be

P(two sixes) + [1 - P(two sixes)]*P(two sixes)

because I can either win the first roll or lose the first one and win the second. Am I right?

I'm pretty sure I am and this is an embarrassingly easy problem to be bothering you guys with, but probability is so unintuitive right now that I decided I'd still ask.

User avatar
phlip
Restorer of Worlds
Posts: 7556
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Math: Fleeting Thoughts

Postby phlip » Sun Mar 27, 2011 12:05 am UTC

rat4000 wrote:Am I right?

Yep.

Though an easier way to calculating your final result is 1 - (1 - P(two sixes))2... which is nicer because you can add, say, a third round easily by changing the squared to a cubed. Noting that (1 - P(two sixes)) is the probability of losing a round, and (1 - P(two sixes))n is the probability of losing all of n (independent) rounds.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

genevabeagle
Posts: 42
Joined: Tue Dec 12, 2006 11:32 pm UTC

Re: Math: Fleeting Thoughts

Postby genevabeagle » Sun Mar 27, 2011 12:15 am UTC

I'm not great with probability, but since the problem says
rat4000 wrote:I win if at least two of the dice are sixes
doesn't P(winning on a roll) ≠ P(two sixes)?

User avatar
rat4000
r/ratsgonewild
Posts: 451
Joined: Mon Feb 09, 2009 7:51 pm UTC

Re: Math: Fleeting Thoughts

Postby rat4000 » Sun Mar 27, 2011 8:36 am UTC

Er, yeah, I meant "two sixes or more" which I can still figure out with a binomial distribution (it's just a different set of values). I'd actually solved it with two sixes or more, then messed up when posting :oops:

phlip: thank you.

User avatar
Dason
Posts: 1310
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Math: Fleeting Thoughts

Postby Dason » Tue Mar 29, 2011 7:40 am UTC

I wish my metropolis algorithm wouldn't take so long to run. Of course I could speed it up considerably if I actually put a little more effort into the parameterization so that I could use independent normals as my proposal and still have good mixing but it runs fine now... I just have to wait a few minutes every time I changed something. Blarg.
double epsilon = -.0000001;

User avatar
phlip
Restorer of Worlds
Posts: 7556
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Math: Fleeting Thoughts

Postby phlip » Sun Apr 10, 2011 6:13 am UTC

My sister's doing an actuarial studies course, and she's looking ahead on the formula sheet to see what's ahead... she's come across one entry that says, for annuities:
[math]E\left [\tilde s_n \right ] = s_n\text{, where }s_n\text{ is evaluated at the interest rate }E\left [\tilde i \right ][/math]
Now, she's told me that [imath]s_n[/imath] is the accumulated value of an annuity after [imath]n[/imath] years, and we've figured out from context that the tilde represents a random variable and [imath]E\left[\tilde x\right][/imath] is expected value... but given that, this just looks wrong. [imath]s_n[/imath] isn't linear in the interest rate, so it doesn't seem right that you should be able to pull the EV out like this.

So I tried it... say you invest $1 per year, at an unpredictable interest rate, that has a 50% chance of being 1%p.a. and a 50% chance of being 2%p.a., compounded yearly, for 20 years. Just for the simplicity. Run the calculations, and you get that at 1% you'd end up with $22.02, and at 2% you'd end up with $24.30. The upshot being that your expected final value is the average of those, which is $23.16... but if you calculate the final value at your expected interest rate of 1.5%, you instead get $23.12. Which isn't equal. And I think in general it will be lower - it's non-linear such that, as the interest rate increases, the gains from increasing the interest rate also goes up (ie [imath]\frac{\partial s_n}{\partial i}[/imath] is increasing...) which means that the distribution of [imath]\tilde s_n[/imath] is going to be more bottom-heavy than that of [imath]\tilde i[/imath], so I'd expect the expected value of [imath]\tilde s_n[/imath] to be higher than [imath]s_n[/imath] at the expected value of [imath]\tilde i[/imath]...

So, for anyone who's seen this formula before: are we missing something? Does it only work if [imath]\tilde i[/imath] is normally-distributed or something? Or is it just an approximation? Or is it just wrong?

I mean, we could just wait a couple of months until they actually cover this in the course proper, but we're confused now, dammit.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Math: Fleeting Thoughts

Postby Macbi » Mon Apr 11, 2011 10:08 am UTC

I imagine that it works out if you take [imath]\tilde i[/imath] to be the geometric mean rather than the arithmetic mean. In your example [math]\tilde i = \sqrt{1.01*1.02} = 1.014987[/math] which looks about right. The GM is always less than the AM as expected.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
phlip
Restorer of Worlds
Posts: 7556
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Math: Fleeting Thoughts

Postby phlip » Mon Apr 11, 2011 12:28 pm UTC

But calculating the result at the arithmetic EV of the interest rate gave a number that was too low... I don't see how using the geometric EV to make it even lower will help...

Unless you meant to take the geometric EV of [imath]\tilde s_n[/imath] too, but that still doesn't close the gap completely. And anyway, that wouldn't help, because it's definitely the arithmetic EV of [imath]\tilde s_n[/imath] that you're trying to calculate.

[edit] Alpha says that the result is equivalent to calculating the [imath]s_n[/imath] at an interest rate of approx 1.515% - higher than the (even arithmetic) EV of the interest rate.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

saxasm
Posts: 4
Joined: Sat Feb 27, 2010 9:51 pm UTC

Re: Math: Fleeting Thoughts

Postby saxasm » Mon Apr 11, 2011 10:11 pm UTC

I found some strange site about the golden ratio, the fibonacci series, and such standard "ohh math is strange and so hard it can't be explained to you" things. Naturally, no proofs of their claims to be found anywhere. I found this ( http://goldennumber.net/pascal.htm ) especially interesting, but of course they don't explain why or prove it.

I managed to boil it down to:
[math]F_n = \sum_{i=0}^\infty \binom{\lfloor\frac{n}{2}\rfloor+i}{\lfloor\frac{n-1}{2}\rfloor-i}[/math]

Now, how would I even start to prove that? I have no idea how you manipulate an infinite sum (that sum could be given an upper bound with [imath]\lceil\frac{n}{2}\rceil[/imath], if I remember correctly, at least in the cases I checked) or a binomial... (I already checked for a few large values, and it seems to hold so far)

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Math: Fleeting Thoughts

Postby jestingrabbit » Mon Apr 11, 2011 10:35 pm UTC

I think the sum you want is perhaps better expressed as [math]F_n = \sum_{i=0}^{\lfloor n/2 \rfloor +1} {n - i \choose i}.[/math] I'm not sure if what you wrote gives the same sums, but its much clearer that its finite now. To prove that these [imath]F_n[/imath] are Fibonacci numbers, ask yourself what is a simple set of properties that uniquely describes the Fibonacci numbers. Does this new sequence share these properties?

I expect you'll want to use the fact that [imath]{n-1 \choose r-1} + {n-1 \choose r} = {n \choose r}[/imath] somewhere.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
phlip
Restorer of Worlds
Posts: 7556
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Math: Fleeting Thoughts

Postby phlip » Mon Apr 11, 2011 11:01 pm UTC

jestingrabbit wrote:Ask yourself what is a simple set of properties that uniquely describes the Fibonacci numbers. Does this new sequence share these properties?

I expect you'll want to use the fact that [imath]{n-1 \choose r-1} + {n-1 \choose r} = {n \choose r}[/imath] somewhere.

I think the result is actually easier to prove directly from Pascal's triangle, using the diagram on that site, than from the nCr form. Though I imagine the proof using one could easily be transformed into a proof using the other, it's just easier to see what the proof would be, looking at the triangle.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Math: Fleeting Thoughts

Postby jestingrabbit » Mon Apr 11, 2011 11:18 pm UTC

I'd say the diagram is a good place to get the idea for the proof, but that you need algebra to really make it rigorous. Sometimes we see what we want to see in diagrams, whereas its much harder to fool yourself with equations.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
diabolo
Posts: 72
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

Re: Math: Fleeting Thoughts

Postby diabolo » Sat Apr 16, 2011 8:25 pm UTC

Hello Math people,
I come to you with a question (not deserving its own thread I think) about permutations.

Let's say I have a function f returning a permutation of a list, I start with any list l0 and apply f on it iteratively until I get back to the original ordering.
For example:

Code: Select all

l0          = [a, b, c, d, e, f, g, h, i, j]
l1  = f(l0) = [c, e, h, f, b, g, d, i, j, a]
l2  = f(l1) = [h, b, i, g, e, d, f, j, a, c]
...
l30 = l0    = [a, b, c, d, e, f, g, h, i, j]

My question is: how can I determine the minimum number of iterations needed to complete the cycle (without actually running it)?

I think I have an answer, but I'm not as good at math as I should be so...
Here's what I have so far, I compute the actual permutation from l0 and f(l0), and then a decomposition into orbits:
[math]\sigma=
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
3 & 5 & 8 & 6 & 2 & 7 & 4 & 9 & 10 & 1\\
\end{pmatrix}
=
\begin{pmatrix}
1 & 3 & 8 & 9 & 10
\end{pmatrix}
\begin{pmatrix}
2 & 5
\end{pmatrix}
\begin{pmatrix}
4 & 6 & 7
\end{pmatrix}[/math]
I believe the number of iterations needed is equal to the least common multiple of the lengths of the orbits, in this case lcm(5,2,3) = 30.
This works on all the random examples I tested but I'd like to know if there is a theorem or something (other than my own "yeah it feels right and it works so far") confirming this?

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Math: Fleeting Thoughts

Postby Dark Avorian » Sat Apr 16, 2011 10:20 pm UTC

Gallian's Contemporary Abstract Algebra confirms that that is indeed the order of the permutation.
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

User avatar
jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Math: Fleeting Thoughts

Postby jaap » Sat Apr 16, 2011 10:20 pm UTC

diabolo wrote:I believe the number of iterations needed is equal to the least common multiple of the lengths of the orbits, in this case lcm(5,2,3) = 30.
This works on all the random examples I tested but I'd like to know if there is a theorem or something (other than my own "yeah it feels right and it works so far") confirming this?

This is correct, and not hard to prove.
Suppose you write a permutation as a product of disjoint cycles, like you just did. For example, if there are three cycles p=xyz. Those cycles commute with each other *, meaning xy=yx. yz=zy, and xz=zx. Using this you can prove ** that pn = xnynzn. The only way this can be the identity, is if each of those factors is the identity ***, so if the orders of x, y, and of z all divide n. The order of p is the smallest such number.
To prove it rigorously, you have to fill in a few steps at *, **, and ***.

User avatar
diabolo
Posts: 72
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

Re: Math: Fleeting Thoughts

Postby diabolo » Sun Apr 17, 2011 7:13 am UTC

I didn't know it was called the order of the permutation *, now that I do I can indeed find various sources stating the lcm property...
Thank you guys for pointing out this name and the sources/proof.

* the little I know about permutations I learned from juggling. That's where I knew the orbits idea from but I wasn't aware it was a legitimate mathematical concept before I looked up the notations in order to ask the question.

saxasm
Posts: 4
Joined: Sat Feb 27, 2010 9:51 pm UTC

Re: Math: Fleeting Thoughts

Postby saxasm » Sun Apr 24, 2011 7:35 pm UTC

Perhaps not as much a fleeting thought as a small question not deserving its own thread, but still.

I were reading a free ebook on group theory, when I suddenly remembered an old maths project I'd been doing about sudokus. Back then I just thought about how you can change a sudoku puzzle without changing its solution (for a program I was making to auto-solve sudokus). So, I'm now thinking of that again, but putting it in neater terminology and using better tools for it. (A barely-into-high-school level of maths knowledge was rather insufficient to make any good progress). So, "symmetry group" (or whatever it should be called, but it feels like that is almost correct... :P ) of a sudoku puzzle. I've chosen to limit myself to the 3x3 larger grid structure, and rotations, since it'd require a pretty ridiculous amount of symbols to represent each row and column swap...

First I labeled each box with 1-9, with the top left box being 1, and proceeding rightwards and then starting leftmost next row, like normal writing. Then I label a pi/2 counterclockwise rotation A, which would be the permutation (1397)(2684). I also label (14)(25)(36) B, (47)(58)(69) C, (12)(45)(78) D and (23)(56)(89) E.

Then draw the conclusions that:
[math]A^4=B^2=C^2=D^2=E^2=I[/math]
[math]BCB=CBC[/math]
[math]EDE=DED[/math]
[math]EDEBCB=BCBEDE=A^2[/math]

I'm not so experienced in group theory, but does anyone see any errors in my thinking or recognize this group structure from somewhere else?

User avatar
rat4000
r/ratsgonewild
Posts: 451
Joined: Mon Feb 09, 2009 7:51 pm UTC

Re: Math: Fleeting Thoughts

Postby rat4000 » Sun May 08, 2011 3:51 pm UTC

Well, here I am again with yet another question not worthy of its own thread. I'm trying to work my theoretical knowledge of integrals into a practical problem.

Say I have a rocket in a vacuum without gravity. The rocket will accelerate at 2m/s2 for 5 seconds, then its fuel will run out. How far will the rocket have gone from its starting place after ten seconds?

Well, the velocity is the antiderivative of acceleration, so if the acceleration is a constant a(t) = 2m/s2, the velocity will be v(t) = ∫a(t)dt = 2t m/s (+c, which we set to zero). The position is the antiderivative of velocity, so s(t) = ∫v(t)dt = t2m (+c, which we set to zero). Then the rocket will have gone 52 = 25m after 5 seconds and will be moving with a speed of 2*5=10m/s, so after another 5 seconds it will have gone another 50m, or 75m in all.

Is there anything wrong in what I wrote?

User avatar
Eebster the Great
Posts: 3103
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Math: Fleeting Thoughts

Postby Eebster the Great » Mon May 09, 2011 2:41 am UTC

rat4000 wrote:Well, here I am again with yet another question not worthy of its own thread. I'm trying to work my theoretical knowledge of integrals into a practical problem.

Say I have a rocket in a vacuum without gravity. The rocket will accelerate at 2m/s2 for 5 seconds, then its fuel will run out. How far will the rocket have gone from its starting place after ten seconds?

Well, the velocity is the antiderivative of acceleration, so if the acceleration is a constant a(t) = 2m/s2, the velocity will be v(t) = ∫a(t)dt = 2t m/s (+c, which we set to zero). The position is the antiderivative of velocity, so s(t) = ∫v(t)dt = t2m (+c, which we set to zero). Then the rocket will have gone 52 = 25m after 5 seconds and will be moving with a speed of 2*5=10m/s, so after another 5 seconds it will have gone another 50m, or 75m in all.

Is there anything wrong in what I wrote?

The only flaw I see in your math is a minor detail about units: The units of t are presumably of time, so you should have a = 2 m/s2, v = 2t m/s2, and x = t2 m/s2. But yes, your answer is correct.

Indeed, you should notice that in equal times, you went half the distance in the first part (when accelerating linearly from 0) as in the second part (when traveling at the constant maximum speed). This is what you should expect.

User avatar
rat4000
r/ratsgonewild
Posts: 451
Joined: Mon Feb 09, 2009 7:51 pm UTC

Re: Math: Fleeting Thoughts

Postby rat4000 » Mon May 09, 2011 7:04 am UTC

Yes, of course. Thank you :)

dissonant
Posts: 63
Joined: Sat Jan 24, 2009 10:33 am UTC

Re: Math: Fleeting Thoughts

Postby dissonant » Tue May 10, 2011 11:44 am UTC

I often wonder about Brouwer's fixed point theorem. I.e "Every continuous function f from a closed disk to itself has at least one fixed point."

Say, by means of an analogy we are stirring a cup of coffee. At any two points in time there is some point which has not moved. Do these fixed points trace out some kind of "path"? I would think so. Intuitively, if the derivative is 0 at a point and the derivatives change continuously over the surface then if you are going to be a fixed point at the next point in time you would need to be arbitrarily close to the original.

Although, I would be happy if fixed point jumped around a lot too...

User avatar
doogly
Dr. The Juggernaut of Touching Himself
Posts: 5453
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, MA
Contact:

Re: Math: Fleeting Thoughts

Postby doogly » Wed May 11, 2011 2:39 pm UTC

I am not sure how directly Brouwer enters, but I know there is some fantastically interesting dynamics:
http://arxiv.org/abs/1004.0639
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests