Wikipedia:Reference desk/Archives/Mathematics/2009 October 23

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 23

Binary trees and transient Markov Chains

Hi all -

I was wondering whether anyone could explain to me why a Markov chain represented by a rooted infinite complete binary tree, with probabilities of 1/3 of moving in each of the 3 directions along each edgr at each vertex, except for the root R of the tree which has probability 1 of moving away from the vertex R, and of course 1/3 of moving towards it from (0,1): i.e.

     R
     |
   (0,1)
    / \
(1,1) (1,2) 
 /\     /\
    ...

is transient? I thought I might see a nice solution by considering the chain of 'height' on the binary tree - i.e. you move down with probability 2/3 and up with probability 1/3, basically a random walk in 1D - then if this is not recurrent it should imply the probability of reaching the same level you were on before is <1, and hence the probability of reaching the same vertex is also <1. If this were a standard p/q left/right random walk, I know how to show that it is recurrent if and only if the probability of moving in each direction is 1/2 - however, the vertex R means the walk isn't infinite in both directions, which ruins my almost-very-nice solution. Could anyone suggest a nice way to show the transience?

On a different note, for a fairly simple birth-death chain (1D with probabilities p_i,q_i of moving in each direction at node i), what's the easiest way to find (*) P(X_n-> infinity as n -> infinity) - e.g. should I be looking at the expected time of something as n tends to infinity, or P(X_n<n) as n tends to infinity, or the number of times each node gets hit, etc? I'm sure once I know a sensible way to show (*), the actual question will be fairly simple, i just have p_i=(i+1/i)^kq_i, p+q=1, p₁=1 if that's relevant, but I'm sure once I know what to aim for, I can do the rest myself.

Thanks a lot, Otherlobby17 (talk) 03:31, 23 October 2009 (UTC)

Certainly identifying together vertices of the graph (that is, collapsing together multiple vertices as a single vertex) will not transform a non-transient chain into a transient chain. So first off get rid of the node R by identifying it with (0, 1). Now, identify together all children of (1, 1) that are the same level (i.e., distance from (0, 1)) as each other (so (4, 3) is identified with (4, 2) but not with (5, 1)), and likewise identify together all children of (1, 2) that are the same level as each other. What you are left with is an infinite 1D list, where the probability of transitioning away from (0, 1) is 2/3 and towards (0, 1) is 1/3 at every node (except at (0, 1) itself). So by whatever logic you had before, this chain must be transient. Eric. 131.215.159.109 (talk) 11:27, 23 October 2009 (UTC)

Actually, what you had originally (which is just a less complicated version of what I wrote above) should work ok, if I understood it correctly. As far as I can tell you don't actually need the 1D random walk to be infinite in both directions for the chain to be transient. Eric. 131.215.159.109 (talk) 11:31, 23 October 2009 (UTC)

Thanks, that's very helpful :) could anyone suggest anything for my second problem perhaps? Otherlobby17 (talk) 14:51, 23 October 2009 (UTC)

I'm not sure if I understand your second problem, nor if, once I understand it, I'd be able to help -- hopefully someone else will be able to give a hand. Eric. 131.215.159.109 (talk) 23:33, 23 October 2009 (UTC)

The Frustrating Integral

How do I solve ʃe^x ln(x) dx ? That is, the integral of the product of the exponential and the logarithm to the base of e, both wrt x ? Thanks. The Russian.202.36.179.66 (talk) 09:25, 23 October 2009 (UTC)

This function has no elementary antiderivative. Using integration by parts, you can express its antiderivative in terms of an exponential integral: $\int e^{x}\log x\ dx=e^{x}\log x-\mathrm {Ei} (x)+C$. -- Meni Rosenfeld (talk) 09:54, 23 October 2009 (UTC)

I use Wolfram alpha whenever I need anything integrated. In this case, it agrees with Meni's answer. Jim (talk) 16:51, 23 October 2009 (UTC)

Back in the old days, we would just use the Wolfram Integrator. Personally I have Mathematica installed so I don't need these middlemen. -- Meni Rosenfeld (talk) 16:05, 24 October 2009 (UTC)

How do I solve $\int x^{x}dx$? --88.77.226.119 (talk) 07:40, 24 October 2009 (UTC)

This one doesn't even have an expression in common special functions (not one that Mathematica can find, anyway). -- Meni Rosenfeld (talk) 16:05, 24 October 2009 (UTC)

Sophomore's dream might be relevant. — Pt _(T) 09:24, 25 October 2009 (UTC)

What is $\int _{0}^{\infty }x^{-x}\,dx$? And $\int _{1}^{\infty }x^{-x}\,dx$? --88.77.252.209 (talk) 19:32, 27 October 2009 (UTC)

Peano axiom of induction

I don't understand where boundaries for arithmetic of natural numbers lay. First-order PA (Peano arithmetic), when regarded from the set theory, have "nonstandard models", those are wrong about what the natural numbers "really" are. It means, that the first-order theory doesn't completely explain what the natural numbers are. Second-order PA, from the other hand, is essentially more then only theory of natural numbers.

As far as I know, the difference consists in interpretation of induction axiom. It requires quantification over all properties of natural numbers, but first-order predicate calculus denies such a trick. The solution of first-order PA is such that it states the axiom for every formula, that defines a property of natural numbers. But the solution collides with the objection: Perhaps there are properties, those cannot be expressed as formulas. The solution of second-order PA is such that it considers as objects of the theory not only natural numbers, but also sets. The last trick allows to change quantification over properties for quantification over sets.

I suppose, that "pure" arithmetic, when stating axiom of induction, should quantify over all properties (expressible as formulas or not), but it shouldn't introduce new objects (those are not natural numbers). Why cannot we consider induction as universal meta-axiom:
For any property $\varphi$ in every theory $T$, if $\varphi (0)\land \forall n~(\varphi (n)\to \varphi (Sn))$, then $\forall n~(\mathbb {N} (n)\to \varphi (n))$?
Here $\mathbb {N}$ - predicate symbol that means "is a natural number".

Property $\varphi$ should be expressible as a formula, but it could be a formula of someting more then arithmetic.

--Eugepros (talk) 10:32, 23 October 2009 (UTC)

Nothing stops you from adding the schema above (it's called full induction) to any theory which has a notion of natural numbers, and in many theories (like ZFC, or in fact PA), this schema is actually provable. So? — Emil J. 10:47, 23 October 2009 (UTC)

Just to clarify, since me and Algebraist below obviously understood the OP in a different way: the full induction schema I'm talking about is the induction schema as above with $\varphi$ an arbitrary first-order formula in the language of the theory in question. — Emil J. 11:22, 23 October 2009 (UTC)

(edit conflict) As I understand it, considering induction as a "universal meta-axiom" with quantification over all possible properties is exactly what the second-order induction axiom does. As for your suggestion that this property be expressible as a formula, I don't think this can give the full power of second-order induction, since (for any reasonable meaning of "formula"), there are only countable many formulae, while there are uncountably many sets of naturals. This approach can certainly give something stronger than first-order PA, though: for example, ZFC proves every instance of induction expressible by a formula of ZFC, allowing it to prove arithmetical statements that PA cannot prove, such as Goodstein's theorem and the consistency of PA. Algebraist 10:50, 23 October 2009 (UTC)

If you use properties definable by formulas outside of the laguage of the theory, then as long as it makes any sense at all, it is equivalent to second-order induction: for any set A of natural numbers, you can take a unary predicate P realized by exactly the elements of A. — Emil J. 11:22, 23 October 2009 (UTC)

Well, yes, if your stronger language allows you to quantify over arbitrary sets, then you're already doing second-order induction. I was just pointing out that first-order ZFC, while not strong enough to prove (or even express) genuine second-order induction, is still capable of proving a much stronger induction scheme than first-order PA. Algebraist 11:32, 23 October 2009 (UTC)

I am not allowing any quantification over sets. I just take the standard model of arithmetic in the language of the Peano arithmetic expanded by a single unary predicate. I can't imagine any coherent definition of "properties definable by formulas outside of the language of the theory" which would rule out this case, but allow ZFC. In fact, what do you mean by properties definable in ZFC here? If you take a formula $\varphi$ in the language of ZFC and a natural number n, both $\varphi (n)$ and $\neg \varphi (n)$ may be consistent with ZFC; the formula only defines a property of natural numbers within ZFC. — Emil J. 11:49, 23 October 2009 (UTC)

I simply meant any property definable by a formula in the language of ZFC (possibly with parameters). ZFC of course proves an induction axiom for each such formula. As for expanding the language of PA with a single unary predicate, and adding induction for that predicate, that doesn't allow you to prove any additional arithmetical statements at all, so I don't see in what sense it is equivalent to second-order induction. Algebraist 11:55, 23 October 2009 (UTC)

Look, I'm just trying to make any sense of the idea that a theory would use induction for properties outside of its language. The only coherent formal meaning of my understanding of your reading of the OP's suggestion I could come up with is as follows: we want a "1½-order theory" whose models M are models of Robinson arithmetic (say) such that for every "suitable" (finite in a finite language, for all I care) theory T and every expansion of M to a model of T, the expansion satisfies induction for all formulas of T. I claim that this "1½-order theory" is in fact a full second-order theory in the sense that its only model is the standard model of arithmetic (and adding a unary predicate realized by any subset of the model is the way to prove this). If this is not what you want, please give a formal definition of what you are talking about. — Emil J. 12:38, 23 October 2009 (UTC)

Also, your explanation of definable in ZFC did not explain anything. Let M be a model of arithmetic, with no particular model of ZFC hanging around. What am I supposed to do to find out whether M satisfies induction for all properties definable in ZFC, according to your definition? — Emil J. 12:53, 23 October 2009 (UTC)

You can't. That definition makes sense only for a model of PA living inside a model of ZFC (by "embedded" I mean canonically embedded, i.e. as the set ω of the model). The point is that by expanding your language to that of set theory, you can express more induction axioms, and (if you also give yourself a powerful enough theory in the expanded language to prove them) you can thereby prove arithmetical statements (i.e. statements in the original language) that you couldn't prove before. Of course, this ability to prove more theorems corresponds to a slimming down in the number of models, so many models of arithmetic cannot be embedded in a model of ZFC in this fashion. Algebraist 16:09, 23 October 2009 (UTC)

Emil J., you were right, I meant quantify over properties "definable by formulas outside of the laguage of the theory". Because quantification over properties definable by formulas inside of the laguage of the theory (induction schema of the first-order PA) gave as non-categorical theory. And I would like to have categorical definition of natural numbers. The second-order PA is categorical, but I'm afraid this inference comes from our specific comprehension of what the "sets" are (ZFC). For example, when I proposed to interpret the second-order PA in General set theory, I was told, that in this case we could not prove its categoricity (and consistency).

So, it was an attempt to state categorical definition of natural numbers without "additional" set-theoretical axioms (such as infinity), because they might look questionable for someone and hadn't concern with the topic (natural numbers). This meta-theoretical principle requires induction schema not only in theory T (which has a notion of natural numbers), but also in meta-theory MT, that will interpret T. The question is: Can MT prove categoricity of natural numbers in T? The idea is that T uses induction for properties $\varphi$, defined inside of the language of MT.

--Eugepros (talk) 16:23, 23 October 2009 (UTC)

In reasonable setups, the second-order induction axiom is equivalent to induction in metatheory (at least for formulas for which the metatheory has separation axioms), so you are unlikely to gain much in this way.

I am not much familiar with GST, but since it does not have any axiom of infinity, its natural numbers (and any other model of Robinson arithmetic, for that matter) may form a proper class. Then there is no good way of even expressing in this metatheory what satisfaction of second-order induction in a (class) model, or isomorphism of two (class) models, means. In fact, it cannot even define the satisfaction predicate for first-order formulas in the standard model of arithmetic. Such a metatheory is simply inadequate wrt the question you are discussing, it is meaningless to ask whether it proves categoricity of second-order arithmetic when it cannot even formulate it. I am fairly confident that categoricity of second-order arithmetic is provable in any reasonable metatheory where it is expressible. — Emil J. 17:11, 23 October 2009 (UTC)

As I understand it, second order quantification in the Peano induction axioms means quantifying over all subsets of N, an uncountable collection. Any scheme involving a recursively enumerable set of axioms and regular first-order logic will be subject to the incompleteness theorem. The first-order theory of true arithmetic has just one countable model, but its axioms are not recursively enumerable. You can also describe true arithmetic with an effective axiomitization and an infinitary inference rule, i.e. ω-logic. 69.228.171.150 (talk) 00:57, 24 October 2009 (UTC)

Emil J., there is the difference between the second-order induction axiom and this induction meta-principle: The second-order induction axiom speaks about any subset of $\mathbb {N}$, even though the corresponding property cannot be expressed in any conceivable language. But this meta-principle speaks about any property, that is expressible in at least one conceivable language. I don't understand in what sense we can speak about unexpressible properties, but the second-order induction axiom actually does it.

Nevertheless, I guess that you are right when speaking about they are equivalent - in the sense of probative force from any first-order metatheory point of view.

Concerning GST: Since it does not have any axiom of infinity, it cannot prove that there is a model of arithmetic. In this sitiation it's wrong to ask: "is that model alone (up to isomorphism)"? But I think, that it's reasonable to ask: Can GST prove, that "if there was a model of arithmetic, then it would be alone up to isomorphism"?

Conserning uncountably many subsets of $\mathbb {N}$: For any given language there are countably many formulas, that express properties of natural numbers - obviously less then subsets of $\mathbb {N}$. But the meta-principle speaks about expressibility in any conceivable language. It's not obvious for me, that there are countably many such languages. Therefore I cannot conclude, that there are countably many properties, matching this induction meta-principle.

--Eugepros (talk) 19:03, 24 October 2009 (UTC)

In a decent metatheory, every subset of the natural numbers is trivially expressible by a property describable by a formula in its language, namely $x\in a$, where a is a parameter (and its value is the set in question). — Emil J. 15:28, 2 November 2009 (UTC)

There are only countably many recursively enumerable languages because the Turing machines are enumerable. There are uncountably many languages (every subset of $\mathbb {N}$ is a language) but if you get rid of the recursive enumerability requirement, the incompleteness theorems no longer hold. See true arithmetic for an example. 69.228.171.150 (talk) 10:20, 27 October 2009 (UTC)

I don't understand what do you mean about recursive enumerability of a language? It's obvious, that any language in a finite alphabet consists of countably many words. But why shouldn't exist uncountably many finite alphabets? Example: if "letter" is any ordinal number, there will be uncountably many finite alphabets of such "letters" (and uncountably many languages).

As far as I know, the incompleteness theorems are valid for every first-order theory, containing arithmetic, in any of such languages.

Concerning true aritmetic or any other theory with uncountably many axioms: I cannot regard it as a proper theory at all, because there is not formally defined way to prove something in such a "theory". Actually, to prove something in TA, we should previously construct a model of PA, and to make it, we should have some modelling theory (a meta-theory for PA).

--Eugepros (talk) 14:27, 28 October 2009 (UTC)

A language is recursively enumerable if there is a Turing machine that can generate all its strings. For example, the theorems of Peano Arithmetic are recursively enumerable, so the language whose strings are those theorems is recursively enumerable. I usually think of formal languages as having to be over finite alphabets, so "any subset of N is a formal language" assumes treating each integer k as (say) a binary digit string, over the alphabet {0,1}. True arithmetic has countably many axioms. It is the theory (i.e. set of sentences) composed of all the first-order arithmetic sentences that are true of the standard natural numbers. It is a perfectly good theory even though there is no Turing machine that can generate all its sentences or axioms. A theory whose sentences can be generated by a Turing machine is called an effective theory, and the incompleteness theorem says that any consistent, effective theory containing arithmetic will necessarily have a sentence G such that neither G nor its negation is in the theory. Since true arithmetic is not an effective theory, the incompleteness theorem doesn't apply. (One does not normally speak of proving theorems in TA; it exists only in the abstract. By Tarski's indefinability theorem, it's impossible to even describe TA in arithmetic terms.)

In computer science lingo, the recursively enumerable languages are the complexity class RE. 69.228.171.150 (talk) 12:10, 29 October 2009 (UTC)

statistics problem

from a set of n element a non empty subset is choosen at random in the sense that all of the non empty subset are equally likely to be selected. let X be the number of elements in the choosen subset. find E(X) and Var(X).220.225.244.114 (talk) 15:55, 23 October 2009 (UTC)

Please do your own homework.

Welcome to Wikipedia. Your question appears to be a homework question. I apologize if this is a misinterpretation, but it is our aim here not to do people's homework for them, but to merely aid them in doing it themselves. Letting someone else do your homework does not help you learn nearly as much as doing it yourself. Please attempt to solve the problem or answer the question yourself first. If you need help with a specific part of your homework, feel free to tell us where you are stuck and ask for help. If you need help grasping the concept of a problem, by all means let us know. AndrewWTaylor (talk) 16:15, 23 October 2009 (UTC)

... but here's a hint. There are ${\binom {n}{k}}$ subsets with k members, so to find E(X) and Var(X) you are going to need closed expressions for $\sum k{\binom {n}{k}}$ and $\sum k^{2}{\binom {n}{k}}$. Binomial_coefficient#Identities_involving_binomial_coefficients is probably a good place to start. Gandalf61 (talk) 16:22, 23 October 2009 (UTC)

thanks for hits sir,i found result but how can i calculate expectation value for the variable x which signifies the number of elements in the choosen subset.i cant calculate rightly.220.225.244.114 (talk) 16:51, 23 October 2009 (UTC)

Okay, here are more hints. For a discrete random variable X that can take values x_i, the expected value of X is

$E(X)=\sum _{x_{i}}x_{i}P(X=x_{i})$

In this case there are 2ⁿ − 1 non-empty subsets so the probability of choosing any given subset is 1/(2ⁿ − 1). Of these subsets, ${\binom {n}{k}}$ subsets have k members, so the probability of choosing a subset with k members is

$P(X=k)={\frac {\binom {n}{k}}{2^{n}-1}}$

and so

$E(X)={\frac {1}{2^{n}-1}}\sum _{k=1}^{n}k{\binom {n}{k}}$

Now you need to simplify this expression by replacing $\sum k{\binom {n}{k}}$ with a closed form expression. Gandalf61 (talk) 07:57, 24 October 2009 (UTC)