Math: Fleeting Thoughts

[Eastwinn]

Stirling's approximation: know it!

Yesssssss. Perfect.

[Macbi]

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

[Talith]

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

[Quaternia]

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...

[Talith]

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.

[Quaternia]

*BUMP* because I think I have a general answer to the OP's question.
Consider the following two person logic game.
\forall x \exists y P(x,y)
Where x \in {a,b} and y \in {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.

[You, sir, name?]

FT:

\log \prod_i k_i = \sum_i \log k_i

I wouldn't accuse it of being particularly useful, but the identity is pretty to look at.

[letterX]

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

[You, sir, name?]

... 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).

[Syrin]

Consider the following two person logic game.
\forall x \exists y P(x,y)
Where x \in {a,b} and y \in {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 \forall x \exists y P(x,y) statement, then there are only 2⁴ games of this type.

[Eebster the Great]

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.

[Dason]

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.

[phlip]

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...

[You, sir, name?]

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

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

So I re-wrote it as

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

Where H is the Heaviside step function. So now

\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)

Is this horrible and wrong, or am I doing it right?

[jestingrabbit]

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".

[Eebster the Great]

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.

[Talith]

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.

[Kurushimi]

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 x_0 = c, and x_{n+1} = x_n^2 - 4x_n + 6, where c can be any starting complex number. You first find fixed points by solving the equation x_n = x_{n+1} 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 x_0 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 x_n's 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 x_0 = c and x_{n+1} = x_n^2 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 isx_{n+1} = f(x_n)), after you've found a fixed point p (interpreted as a complex number), you look at a function g(x,p)
g(x,p) = |x-p|^2 - |f(x)-p|^2

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.

[rat4000]

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.

[phlip]

Am I right?

Yep.

Though an easier way to calculating your final result is 1 - (1 - P(two sixes))²... 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))ⁿ is the probability of losing all of n (independent) rounds.

[genevabeagle]

I'm not great with probability, but since the problem says

I win if at least two of the dice are sixes

doesn't P(winning on a roll) ≠ P(two sixes)?

[rat4000]

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

phlip: thank you.

[Dason]

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.

[phlip]

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:

E\left [\tilde s_n \right ] = s_n\text{, where }s_n\text{ is evaluated at the interest rate }E\left [\tilde i \right ]

Now, she's told me that s_n is the accumulated value of an annuity after n years, and we've figured out from context that the tilde represents a random variable and E\left[\tilde x\right] is expected value... but given that, this just looks wrong. s_n 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 \frac{\partial s_n}{\partial i} is increasing...) which means that the distribution of \tilde s_n is going to be more bottom-heavy than that of \tilde i, so I'd expect the expected value of \tilde s_n to be higher than s_n at the expected value of \tilde i...

So, for anyone who's seen this formula before: are we missing something? Does it only work if \tilde i 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.

[Macbi]

I imagine that it works out if you take \tilde i to be the geometric mean rather than the arithmetic mean. In your example

\tilde i = \sqrt{1.01*1.02} = 1.014987

which looks about right. The GM is always less than the AM as expected.

[phlip]

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 \tilde s_n too, but that still doesn't close the gap completely. And anyway, that wouldn't help, because it's definitely the arithmetic EV of \tilde s_n that you're trying to calculate.

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

[saxasm]

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:

F_n = \sum_{i=0}^\infty \binom{\lfloor\frac{n}{2}\rfloor+i}{\lfloor\frac{n-1}{2}\rfloor-i}

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 \lceil\frac{n}{2}\rceil, 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)

[jestingrabbit]

I think the sum you want is perhaps better expressed as

F_n = \sum_{i=0}^{\lfloor n/2 \rfloor +1} {n - i \choose i}.

I'm not sure if what you wrote gives the same sums, but its much clearer that its finite now. To prove that these F_n 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 {n-1 \choose r-1} + {n-1 \choose r} = {n \choose r} somewhere.

[phlip]

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 {n-1 \choose r-1} + {n-1 \choose r} = {n \choose r} somewhere.

I think the result is actually easier to prove directly from Pascal's triangle, using the diagram on that site, than from the ⁿC_r 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.

[jestingrabbit]

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.

[diabolo]

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:

\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}

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]

Gallian's Contemporary Abstract Algebra confirms that that is indeed the order of the permutation.

[jaap]

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 pⁿ = xⁿyⁿzⁿ. 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 ***.

[diabolo]

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]

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... ) 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:

A^4=B^2=C^2=D^2=E^2=I

BCB=CBC

EDE=DED

EDEBCB=BCBEDE=A^2

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?

[rat4000]

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/s² 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/s², 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 = t²m (+c, which we set to zero). Then the rocket will have gone 5² = 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?

[Eebster the Great]

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/s² 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/s², 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 = t²m (+c, which we set to zero). Then the rocket will have gone 5² = 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/s², v = 2t m/s², and x = t² m/s². 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.

[rat4000]

Yes, of course. Thank you

[dissonant]

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...

[doogly]

I am not sure how directly Brouwer enters, but I know there is some fantastically interesting dynamics:
http://arxiv.org/abs/1004.0639