Wikipedia:Reference desk/Archives/Mathematics/2009 April 18

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.

April 18

Conditional probability in LaTeX

Does anyone know how to do the "bar" or "given" in LaTeX, besides "|"?

I mean:

$P(B|A)={\dfrac {P(A|B)P(B)}{P(A)}}$

looks fine, but when we start putting bigger text (say, unions):

$P\left(\bigcap _{i=1}^{k}E_{i}\right)=P(E_{1})P(E_{2}|E_{1})P(E_{3}|E_{1}\cap E_{2})\dots P\left(E_{k}|\bigcap _{j=1}^{k-1}E_{j}\right)$

looks poor, so I have to kludge things:

$P\left(\bigcap _{i=1}^{k}E_{i}\right)=P(E_{1})P(E_{2}|E_{1})P(E_{3}|E_{1}\cap E_{2})\dots P\left(E_{k}\left|\bigcap _{j=1}^{k-1}E_{j}\right.\right)$

However, the spacing seems a bit off. I was wondering if there was anything like \colon in LaTeX, which has better spacing:

$\Omega _{1}:\mathbb {R} \to \mathbb {R} \qquad {\mbox{vs.}}\qquad \Omega _{2}\colon \mathbb {R} \to \mathbb {R}$

Thanks in advance. x42bn6 Talk Mess 00:43, 18 April 2009 (UTC)

If you use the amsmath package, you can get different sizes with appropriate spacing use \bigm|, \Bigm|, \biggm|, \Biggm| . Unfortunately they don't work in Wikipedia markup. Once you get used to \bigm, also use \bigl and \bigr (and bigg, Big, Bigg) and leave \left and \right for cases like huge matrices where their bad choices (look how the extra -1 in your example caused the size to jump up) and gratuitous spacing (look at the huge space after your Ps) don't matter. McKay (talk) 04:02, 18 April 2009 (UTC)

Other useful commands are \vert and \vrule; experiment to see how they look for you. I wrote a custom command as follows:

\newcommand {\set} [2] {\left\{#1\ \vrule\ #2\right\}}

to get the appearance I want, and just invoke the command like \set{x \in \Q}{x^2 < 2} to get the set of rationals with square less than 2. Another useful trick is the \vphantom command:

\newcommand {\set} [2] {\left\{#1 \left| \vphantom {#1} #2 \right. \right\}}

The \vphantom command places an invisible box of zero width and height equal to the height of its argument. Eric. 131.215.159.99 (talk) 09:02, 18 April 2009 (UTC)

How about this?

$$P\left(E_k\ \left|\quad \sum_{j=1}^{k-1}E_j\right.\right)$$

You may replace \quad by \,\, or other spacing control sequences. twma 05:35, 19 April 2009 (UTC)

Uniform population sampling noise

Hi Wikipedians:

In the statistics textbook I am reading right now it says that a sample of size 5000 taken from a uniform population with a = 0 and b = 10000 would be subject to more sampling noise than a sample of size 5 taken from a uniform population with a = 0 and b = 10.

I am wondering why that would be the case? I googled "sampling noise" but could not find any definition of "sampling noise" in a statistical context.

Thanks,

76.65.13.187 (talk) 02:25, 18 April 2009 (UTC)

I assume that sampling noise refers to the variability of an estimate of a population parameter. For a uniform continuous distribution between a and b, the SD of the sample mean (for example) is (b-a)/root(12n), giving 40.8 and 1.29 respectively for your two cases, i.e. the first has more uncertainty and hence "noise". I'm not surprised that you could find nothing in a simple statistical context, as noise is usually taken to be something unwanted which is added to a signal, causing trouble in its reading or processing. The innate variability of an estimate, which I think that you are asking about, isn't the same thing at all.Special:Contributions/86.148.186.106|86.148.186.106]] (talk) 09:39, 18 April 2009 (UTC)

Thanks! That is exactly it! And indeed, everything I could google about "sampling noise" is in terms of digital signal processing (DSP) and such. 76.65.13.187 (talk) 14:05, 18 April 2009 (UTC)

See sampling error, shot noise etc. 66.127.52.118 (talk) 09:02, 19 April 2009 (UTC)

(n-1)-size linearly independent subsets of n vectors

If every (n-1)-size subset of the vectors $a_{1},...,a_{n}$ is linearly independent, is it also the case that the full size n set of vectors is necessarily linearly independent? I'm leaning towards yes, but I'm not sure how to prove it - I don't imagine it has a very complicated proof, it just seems to be going over my head right now. Thanks, Otherlobby17 (talk) 05:55, 18 April 2009 (UTC)

n=2 provides a counterexample. Bo Jacoby (talk) 06:25, 18 April 2009 (UTC).

And if you want it for a given n: take n-1 linearly independent vectors, $a_{1},...,a_{n-1}$, and define $a_{n}:=a_{1}+...+a_{n-1}$. --84.221.69.233 (talk) 07:49, 18 April 2009 (UTC)

I'm just wondering here ... a more amusing question would be, given n vectors, any m of which are linearly independent, what is the minimum possible dimension of the space spanned by the n vectors? Ray^Talk 07:55, 18 April 2009 (UTC)

m —Preceding unsigned comment added by 84.221.69.233 (talk) 09:25, 18 April 2009 (UTC)

For infinite fields, the answer is m. For finite fields, the formula will be more complicated: for example, consider $n=q^{m}+1$ vectors over the field of q elements, any m of which are linearly independent. Certainly those n vectors must span a space of dimension strictly greater than m. Eric. 131.215.159.99 (talk) 10:38, 18 April 2009 (UTC)

For infinite fields of nonzero characteristic, is the answer always m?

Yes. For any infinite field F, one can find n vectors in F^m such that any m of them are independent. Algebraist 19:48, 22 April 2009 (UTC)

Is a given set of group elements a set of coset representatives?

If G is a group and if g1, ..., gn are elements of G, is there a criterion or an algorithm (or a function in some dedicated program, like GAP) to determine whether there is a subgroup of G such that those elements form a set of representatives for the cosets of the subgroup? (We may assume that G is a finite permutation group, and probably even the full symmetric group.)

(There are of course several algorithms to find the cosets of a given subgroups, like Todd-Coxeter algorithm; this is a kind of inverse question.)

Thanks! Goochelaar (talk) 12:41, 18 April 2009 (UTC) (Apparently I had not signed. Sorry!)

If g1 and g2 are both in the same right coset of a subgroup H, then g1 g2^-1 is in H. And vice versa. So let H be the subgroup generated by all products gi gj^-1 — if that doesn't work nothing does. To make it more efficient, note that (gi gj^-1)(gj gk^-1) = gi gk^-1, so it suffices to use any set of pairs gi gj^-1 for which the digraph with edges i->j is strongly connected (such as a directed cycle). McKay (talk) 12:24, 18 April 2009 (UTC)

Reading your question more carefully, you want to know if g1,...,gn is an entire coset. That is true iff {g1 gi^-1 | i=1..n} is a subgroup. My more general procedure above finds the smallest subgroup H such that g1,...,gn are contained in the same coset of H. McKay (talk) 12:33, 18 April 2009 (UTC)

Thanks a lot, but I am afraid I was not clear. I am interested in understanding whether the elements g_i form a set of coset representatives, i.e. a transversal, for some subgroup, not a single coset. Goochelaar (talk)

Ooops, your words were clear enough, it was my eyes that were the problem. :) McKay (talk) 13:57, 18 April 2009 (UTC)

I don't see a much better way than to enumerate the subgroups of index n and check for each. The Todd-Coxeter algorithm takes a finite index subgroup given by generators of a finitely presented group and gives the multiplication amongst coset representations. The inverse problem to my way of thinking is starting with the multiplication amongst coset representatives, try to get a finitely presented group with finite index subgroup given by generators. This is well studied and GAP has fairly efficient functions for it. Of course, it will only return a quotient of the original group by the core of the finite index subgroup. JackSchmidt (talk) 17:48, 18 April 2009 (UTC)

I haven't found anything for the general problem (which seems like a reasonable combinatorics type question) of: (1) determining if a subset of a permutation group is a transversal of a subgroup, and if so (2) determining the subgroup from its transversal. I'd be interested to hear a solution. Again, with more information you might have better luck. For instance if the subgroup is known to be a point stabilizer, then you just look at the images of that point under the proposed transversal. JackSchmidt (talk) 20:05, 18 April 2009 (UTC)

Another problem that seems similar is to determine the subgroups that don't include any of some given set of elements. In the original problem we know that the products gi gj^-1 (i ≠ j) all lie outside the subgroup. I think that any subgroup of order n that satisfies that property is a solution, and I don't see why it should be unique. McKay (talk) 07:07, 19 April 2009 (UTC)

That's what I was thinking too. If we consider e.g. the set

$H^{*}:=\{h\in G\,:\,h^{k}\neq g_{i}g_{j}^{-1}\,\forall k,i,j\,;\,i\neq j\}$,

the problem can be restated as: find $\scriptstyle H\subset H^{*}$ which is a subgroup of G of index n. This gives a first necessary condition like $\scriptstyle \mathrm {card} (H^{*})\geq \mathrm {card} (G)/n$. Then, my experience in algebra is too poor to understand if one can go any further in this direction. --pma (talk) 12:25, 19 April 2009 (UTC)

A friend of mine and I were discussing the OP's question, and eventually reached the same conclusion as you (that any subgroup of the right index excluding those elements works). It is also easy to see that if you can solve them problem for a group G, then you can solve it for any subgroup of G; thus solving the problem for the full symmetric group yields a solution for any finite group (and is thus the hardest case). After calculating the number of subgroups of the n-th symmetric group to be $e^{\Theta (n^{2})}$ he decided that the problem was probably intractable. I am not fully convinced that it is intractable but don't see any reasonable way to approach the problem.

One idea is to start with H being the trivial group, and starting adding elements of $H^{*}$ to the generators of H until H cannot be made any larger; then we have a maximal subgroup of G subject to the condition of being a subset of $H^{*}$. The trouble is it might be too small. If somehow in this manner we could enumerate all maximal subgroups of G that are subsets of $H^{*}$, then the desired H must be one of them, but there's seems no obvious non-exponential way to do that.

For G cyclic the problem is trivial. For $G=(\mathbb {Z} /p\mathbb {Z} )^{2}$ we were unable to make much progress. Eric. 131.215.159.99 (talk) 19:33, 19 April 2009 (UTC)

Yes, the combinatorics is so rich that what you say seems the most reasonable procedure. Or checking all subgroups of index n as JS said. Such a set of representatives looks like a very cryptic object to me (a naive observer, as I told). Here's just an analogy, with an infinite group: if G is $\scriptstyle \mathbb {R}$ and the unknown subgroup H were $\scriptstyle \mathbb {Q}$, any set of representatives for the cosets of H would be a Vitali set: thus not even measurable; so a complicated object that we can only state its existence as a direct consequence of the axiom of choice. This somehow suggests that in general the complexity of such sets of representatives, for finite, even abelian groups, should become untractable for large n.--pma (talk) 08:29, 20 April 2009 (UTC)

Here is the OP again. First of all, thanks to everybody for the food for thought. I am glad I had not missed something terribly obvious. Then, here is how I posed myself such a question. I am investigating (structureless, a priori) sets of permutations with certain properties, and the small degree cases gave me a hunch that those sets might be transversals of suitable subgroups (among other things, they may wlog contain the identity but it is not necessary, have a size dividing n! and more), so I wanted to check this in the next few known examples. So I wondered whether this check was easy to do, before launching myself in a brute-searchish computer search or, as a last resort, some serious thinking. :) Goochelaar (talk) 17:10, 20 April 2009 (UTC)

It would help to have more specific numbers. In the next few examples about how many permutations are there and how many moved points? How large is the subgroup generated by the permutations? JackSchmidt (talk) 19:54, 20 April 2009 (UTC)

Critical graph

Hello. I wish to prove that a 3-critical graph is an odd cycle. All I can think of is that since biparitite graphs have chromatic number 2 so the graph cannot have even cycles (that it has cycles is assured for otherwise it would be a tree, which also has chromatic number 2) and hence definitely contains an odd cycle. But I can't think any further. Any help please.--Shahab (talk) 20:02, 18 April 2009 (UTC)

I think you are done? A 3-critical graph is a graph that is not bipartite, but removing any edge produces a bipartite graph? So every odd cycle is 3-critical, and if a 3-critical graph has an odd cycle, then it *is* an odd-cycle (since removing some other edge leaves an odd cycle, so a non-bipartite graph). If the graph is an even cycle, then it is bipartite, so it is not 3-critical. If the graph has an even cycle and removing an edge from the cycle results in a bipartite graph, then restoring the edge remains a bipartite graph. Hence a 3-critical graph has no even cycles. As you say, a graph without cycles is a tree, so bipartite, so not 3-critical. Hence every 3-critical graph is an odd cycle. JackSchmidt (talk) 20:13, 18 April 2009 (UTC)

Thanks. I can't believe what a big idiot I was.--Shahab (talk) 20:18, 18 April 2009 (UTC)