Wikipedia:Reference desk/Archives/Mathematics/2009 September 25

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.

September 25

Number of possible permutations in the lottery

I've been trying to calculate the odds of winning our national lottery, but there is a rule in the permutations and I want to know if there's a formula that works for it.

In the South African lottery, the ball set consists of numbers 1 through 49.
A single lottery ticket/game has 6 of your chosen numbers.
So how many possible combinations of numbers are there?

The problem is that in your series of 6 numbers, a number cannot be <= ^{less than or equal to} the previous number.

In other words the formula isn't 49 ^ 6 ^{49 to the power of 6} nor is it 49 x 48 x 47 x 46 x 45 x 44.

Thanks Rfwoolf (talk) 11:39, 25 September 2009 (UTC)

It's not a permutation, it's an unordered selection. Ie. you select 6 numbers, but the order of those does not matter. The actual number you are looking for is 49!/(43!*6!). Taemyr (talk) 11:43, 25 September 2009 (UTC)

• It's     $C_{6}^{49}={49 \choose 6}=13,983,816$   — see Combination#Number of k-combinations from a set. --CiaPan (talk) 12:29, 25 September 2009 (UTC)

The above answers are correct, but I feel that a little explanation might be in order. You have 49 balls and you draw 6 of them. You have 49 to choose from for your first ball, 48 for the second, 47 for the third, 46 for the fourth, 45 for the fifth, and 44 for the sixth. That gives 49 × … × 44 ways. But you're not interested in the order that they came out in. So, how many ways can you re-arrange the order that the six balls came out in? Well you have six balls to choose for the first ball to come out, five for the second, four for the third, three for the fourth, two for the fifth, and one for the sixth. There are 6 × 5 × … × 1 orders in which the six balls could have been drawn. So in total there are

${\frac {49\times \cdots \times 44}{6\times 5\times \cdots \times 1}}=13,983,816$

ways of choosing six balls from 49 when the order doesn't matter. ~~ Dr Dec (Talk) ~~ 22:57, 25 September 2009 (UTC)

I would guess that they draw 6 balls out of a pool of 49, then arrange them from highest to lowest, just for convenience, as the actual order doesn't matter. StuRat (talk) 13:22, 26 September 2009 (UTC)

Of course, that's exactly what they do. ~~ Dr Dec (Talk) ~~ 22:13, 26 September 2009 (UTC)

with the size of the Lotto jackpots recently who would want to play anyway? even the mathematically stupid don't want to play for "only" R3 million. Of course the above answers demonstrate WHY playing the lotto is a surefire way to lose money, your chances are slim-to-none. Zunaid 22:41, 26 September 2009 (UTC)

I like the story of a someone (Dogbert ?) who sold "day-old" (that is, expired) lottery tickets for half the original price. He argued that he was doing people a favor, since the original $2 ticket only returned 10%, so, represented a $1.80 loss, while the half price expired tickets cost $1, all of which was lost. So, it could be argued that you saved 80 cents by buying an expired ticket. (Of course, if you buy two expired tickets instead of a single good one, that logic breaks down.) StuRat (talk) 15:19, 27 September 2009 (UTC)

Zunaid: playing the lottery is not a "surefire way to lose money". I can only find a stat from May 2006, but up to then the British lottery had made almost 2,000 people millionaires. If it were "surefire" then surely that number should be zero? That's not to mention the smaller prizes given out and, in Britain at least, the £9.5 billion given to good causes by the end of 2008. Besides that, it's quite fun... it only costs £1 to play and you get 10 or 15 minutes of fun thinking about what you might do with the money if you did happen to win. Compare that to almost £3 for a pint and it seems like a healthy, and possibly profitable, bit of fun. ~~ Dr Dec (Talk) ~~ 16:27, 27 September 2009 (UTC)

OK, talking about dreams, I have a dream too. Lotteries: suppressed. Horoscopes: suppressed. Television: suppressed. Discos: suppressed. Soccer: suppressed, with the exception of recreational local clubs. Functional Analysis: mandatory for everybody in the public administration. Don't worry: just a re-educational program for the after-berlusconi Italy. And I had an idea about the Vatican too... oh yes: Vatican: suppressed.--pma (talk) 19:54, 27 September 2009 (UTC)

• Thanks for the answers folks, but are you sure they take into account that numbers combinations aren't repeated? You will see what i mean if you open a spreadsheet (e.g. excel) and start playing around. In our scenario, when we eventually get our first ball to '10', our second ball cannot be 1 to 10, it can only be 11 to 49 because all combinations of 1 and 10 have already been listed at this point, and only combinations between 10 and 11to49 are incomplete. Capish? Rfwoolf (talk) 22:28, 27 September 2009 (UTC)

You really need to explain what you mean. Each lottery draw is an independent event, so that numbers drawn this week do not depend on the numbers drawn last week and they do now effect the numbers drawn next week. What do you mean by getting a first ball to '10'? I think you need to specify the rules of you lottery because it doesn't seem to be like any lottery I have every seen. ~~ Dr Dec (Talk) ~~ 22:35, 27 September 2009 (UTC)

I am not talking about the actual drawing itself, I was talking about writing out each and every ball combination to calculate the number of possible calculations. You said that with the first ball you have 49 options, with the second only 48 and the third only 47, etc, but that logic starts to fail because, when writing out each and every possible combination, start in numerical order from 1, you cannot draw a ball less than the previous number -- something you will understand properly if you do try to write it all out. Let's do a quick example, here we go: 1, 2, 3, 4, 5, 6; 1, 2, 3, 4, 5, 7; 1, 2, 3, 4, 5, 8... Fast forward to 10, 11, 12, 13, 14, 15. Here we have 39 options for ball one, only 38 for ball two, 37 for ball three etc, and you will note that each ball cannot be lower than the previous ball. In our example, we would never go 10, 11, 12, 13, 14, 1; because the combination of 1, 10, 11, 12, 13, 14 was done already a long time back, same as 10, 9, 12, 13, 14, 15; because 9, 10, 12, 13, 14, 15 has already been done. Rfwoolf (talk) 23:38, 27 September 2009 (UTC)

The logic doesn't fail at all. Just read what I wrote carefully. You start of by assuming that the order in which the balls are drawn matters, i.e. 1, 2, 3, 4, 5, 6 is different to 1, 3, 2, 4, 5, 6, and they are both different to 2, 1, 3, 6, 5, 4. In this case there are 49 × 48 × … × 44 possible combinations: you have 49 balls to chose from for the first ball, then there are only 48 balls left from which you choose the second ball, then there are only 47 balls from which you choose the third ball, etc. So there are 49 × 48 × … × 44 possible draws that can be made, there are 49 × 48 × … × 44 different ways the balls can come out of the machine. But, after the balls have been drawn the numbers are put into ascending order, because it's not actually the order that counts, just the balls that came out: If you chose 1, 2, 3, 4, 5, 6 as you numbers then you would win if the draw came 1, 2, 3, 4, 5, 6 or if it came 1, 3, 2, 4, 5, 6 or if it came 2, 1, 3, 6, 5, 4. Well, how many ways are there to reorder the numbers 1, 2, 3, 4, 5, 6? Well we have 6 balls to choose as the first ball, then there are five left to choose the second ball, then there are four left from which to choose the third ball, etc. There are 6 × 5 × … × 2 × 1 ways or reordering 1, 2, 3, 4, 5, 6. So there are, as we have all said above, (49 × 48 × … × 44) / (6 × 5 × … × 2 × 1) = 13,983,816 ways of chosing 6 balls from 49 when the order doesn't matter. This is also, by definition, the number of ways you can write ascending 6-tuples of numbers from 1 to 49. If you still think that the logic fails, try your spreadsheet method with a simpler example: choose 2 balls from 4. Reapply my logic above and you will get that there are (4 × 3) / (2 × 1) = 6 ways you can do it when the order doesn't matter. And look: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} − 6 ways! If you still don't believe me then check out the national lottery article where it says the odds are 13,983,815-to-1, i.e. 13,983,815 losing combinations and 1 winning one, i.e. a total of 13,983,816 combinations. If you still don't get it then, as CiaPan suggested, read the combination article and in particular this section. ~~ Dr Dec (Talk) ~~ 08:59, 28 September 2009 (UTC)

Null hypothesis "trueness"?

If those familiar would comment on this, it would be helpful. Thanx! DRosenbach ^{(Talk | Contribs)} 12:35, 25 September 2009 (UTC)

If I understand you correctly, you claim that the definition of p-value ("the probability of rejecting the null hypothesis when the null hypothesis is true") should be replaced with the definition "the probability of rejecting the null hypothesis when the null hypothesis is unrejectable." I don't believe that your definition is correct (apart from the likely circular argument that arises from the use of the word "unrejectable"). The p-value is predicated on the *assumption* that the null hypothesis is true. Hence, we report the probability of observing what we did observe given the assumption. Wikiant (talk) 15:22, 25 September 2009 (UTC)

Straightforwardly, the equivalent "doing something when it can't be done" is nonsense. So live with the usage that has been commonly accepted for decades. We're talking about a conditional probability, the "given" basis is that the null hypothesis is true. I'll make the further point that the reference desk, as has been said before, is for readers' questions and not for editors to discuss the fine detail of articles.→81.153.220.122 (talk) 08:17, 26 September 2009 (UTC)

Isomorphism between the space of infinite R-valued sequences and the space of polynomials on R

How would one begin showing whether or not there exists an isomorphism between the space of polynomials: $\mathbb {R} \to \mathbb {R}$ and $\mathbb {R} ^{\mathbb {N} }$, the space of infinite sequences in the reals? I can see how the polynomials, which must have a maximum degree for any polynomial, would be isomorphic to the space of sequences with only finitely many nonzero terms, with the obvious bijection between coefficients and terms in the sequence, and this must be contained in $\mathbb {R} ^{\mathbb {N} }$, but I have a feeling the latter may have an uncountable basis whilst the former has the obvious countable basis e_i=(0,0,...,1,0,0,...) with the 1 in the i-th position - but how would I show such a thing if so?

Otherlobby17 (talk) 15:51, 25 September 2009 (UTC)

Hey I don't know much algebra but I think I have a few ideas for you. Like you said, the polynomial space is isomorphic to all eventually 0 sequence space, so if you can show there's no isomorphism between R^N and the space of all eventually 0 space you're done. A good reason for me to believe this is true is: if we replace R, the real numbers, by Q, the rationals, then the cardinality of Q^N is greater than the cardinality of the space of all eventually 0 sequences with rational entries, the first being continuum size and the latter being countable, hence there can be no isomorphism. Breath of the Dying (talk) 16:31, 25 September 2009 (UTC)

You're mistaken. It's easy to show there's no isomorphism between Rⁿ and the space of all eventually zero sequences. But that doesn't answer the question at all. Michael Hardy (talk) 16:33, 25 September 2009 (UTC)

Oh, you meant R^N. Michael Hardy (talk) 16:34, 25 September 2009 (UTC)

An isomorphism is a structure-preserving bijection. But which structure do you want to preserve? Addition of polynomials? Multiplication by scalars? If just those two, then it's vector-space isomorphism. Then there's multiplication of polynomials by each other, making it an algebra isomorphism. The set of sequences with only finitely many nonzero terms is algebra-isomorphic to the algebra of polynomials in an obvious way (see Cauchy product). But if you want to include sequences with infinitely many nonzero terms, then there's the question of how you could multiply them in a way that corresponds to multiplication of polynomials. I don't have an answer to that one. But now let's look at your mention of dimension. The vector space spanned by the countable basis is the set of all finite linear combinations of the basis vectors. If there's no countable basis for the vector space of all sequences of reals, then there's no vector-space isomorphism. And then a fortiori no algebra isomorphism. Right now I don't have that answer either—it seems as if there should be some obvious way to show there's no countable basis. Maybe later.... Michael Hardy (talk) 16:33, 25 September 2009 (UTC)

Let S be an independent system on N of size 2^ω (meaning a set $S=\{X_{\alpha }\mid \alpha <2^{\omega }\}$ of subsets of N such that for every finite sequence $\alpha _{1}<\alpha _{2}<\dots <\alpha _{k}<2^{\omega }$ and $e_{1},\dots ,e_{k}\in \{0,1\}$, $X_{\alpha _{1}}^{e_{1}}\cap \dots \cap X_{\alpha _{k}}^{e_{k}}\neq \varnothing$, where $X_{\alpha }^{0}=X_{\alpha }$, $X_{\alpha }^{1}=\mathbb {N} \setminus X_{\alpha }$.). Then characteristic functions of elements of S form a linearly independent subset of R^N, hence the latter linear space has dimension at least 2^ω. — Emil J. 16:38, 25 September 2009 (UTC)

In fact, one does not even need the system to be fully independent, it suffices that no element of S is covered by a finite union of other elements of S. Any almost disjoint system also has this property, for instance. — Emil J. 16:43, 25 September 2009 (UTC)

ec Indeed, they are not linearly isomorphic, for the space $\mathbb {R} ^{\mathbb {N} }$ has uncountable dimension. While waiting for the algebraic proof here's a topological proof: the space $\mathbb {R} ^{\mathbb {N} }$ is (admits a structure of) a Fréchet space: in particular, is a topological linear space topologized by a complete metric. Hence it can't have countable dimension. Proof: if such a space has countable dimension, it is union of countably many linear finite dimensional subspaces, which are in particular closed subsets with empty interior: but that's impossible by the Baire category argument.(If you prefer to use Banach spaces or Hilbert spaces, just observe that $\mathbb {R} ^{\mathbb {N} }$ has $\ell ^{2}$ as a subspace, already with uncountable dimension for the same reason) --pma (talk) 16:49, 25 September 2009 (UTC)

Emil, does this work? for any real number $\alpha$ in [0,1] let $u_{\alpha }:\mathbb {N} \to 2$ be a binary sequence such that the frequency of 1's tend to $\alpha$. (it can be choosen canonically, it seems to me). Then, it seems that these are a linearly independent set. --pma (talk) 17:06, 25 September 2009 (UTC)

You mean that the asymptotic density of $u_{\alpha }^{-1}(1)$ is $\alpha$? I don't think that this is a sufficient condition to ensure linear independence. For example, assume that the choice is made in such a way that $u_{1/2}^{-1}(1)=\{6n+0,1,2\mid n\in \omega \}$, $u_{1/3}^{-1}(1)=\{6n+3,4\mid n\in \omega \}$, $u_{1/6}^{-1}(1)=\{6n+5\mid n\in \omega \}$, $u_{1}^{-1}(1)=\omega$. Then $u_{1}=u_{1/2}+u_{1/3}+u_{1/6}$, so they are not linearly independent. — Emil J. 17:22, 25 September 2009 (UTC)

Yes, I apologize: I was as late and in a hurry as the March Hare, so I posted without thinking, and left, and when I started thinking, it was too late. Anyway, the correct thing is: define, for all real $\alpha ,$ the sequence $u_{\alpha }$ as a binary sequence with the k-th 1 at the place $\lfloor e^{\alpha k}\rfloor$. Then no finite nontrivial linear combination of these $u_{\alpha }$ may be zero. (their supports $u_{\alpha }^{-1}(1)$ have the property stated by Emil 2h:20 ago, at least in this weak form, still sufficient: in any finite collection of them, at least one -the one with smaller α- is not covered by the union of the others). --pma (talk) 19:24, 25 September 2009 (UTC)

PS: also, we can fix the first construction choosing the family $u_{\alpha }$ to be monotone wrto $\alpha .$ To make the construction, it is sufficient to define the monotone $u_{\alpha }$ for all dyadic $\alpha$, then extend. --pma (talk) 18:51, 26 September 2009 (UTC)

But in fact, an even simpler uncountable linearly independent set is just the family of sequences $v_{\alpha }\in \mathbb {R} ^{\mathbb {N} }$ for all $\alpha >0$, where $v_{\alpha }$ is the exponential sequence with base $\alpha$, that is the sequence $v_{\alpha }(k):=\alpha ^{k}$ for all $k\in \mathbb {N}$. Then it is standard that they are linearly independent, for a proper linear combination:

$\sum _{i=1}^{n}c_{i}v_{\alpha _{i}},$

say with $\alpha _{1}>\alpha _{2}..>\alpha _{n}$ and $c_{1}\neq 0$ can't be zero, just because

$\sum _{i=1}^{n}c_{i}\alpha _{i}^{k}=c_{1}\alpha _{1}^{k}(1+o(1))$ as $k\to \infty$. --pma (talk) 19:24, 25 September 2009 (UTC)

And if you want to see the linear independence of the above $v_{\alpha }$ algebrically, the fact is that n of them are already independent in the projection over the first n coordinates k=0,1,..,n-1 : use the Vandermonde matrix (and note that the wiki-article has it already written with the $\alpha _{i}.$ ). --pma (talk) 23:26, 25 September 2009 (UTC)

Or, for another topological proof: the subspace $\ell ^{\infty }$, has uncountable dimension, for otherwise it was separable with its standard norm. But it is not. (It contains the uncountable family of characteristic functions of all subsets of $\mathbb {N}$, that have uniform distance 1 from each other). --pma (talk) 23:26, 25 September 2009 (UTC)

Also, the subspace $\ell ^{2}$ with its Hilbert norm is isomorphic to $L^{2}([0,1])$, that admits the uncountable chain of subspaces $L^{2}([0,\alpha ])$, $0\leq \alpha \leq 1$--pma (talk) 18:51, 26 September 2009 (UTC)

Summary for the OP. Now you have: a combinatorial proof, following the lines of EmilJ's post. It is the most general, for it also works for $k^{\mathbb {N} }$; it exploits the fact that linear indipendence of a special family of sequences may be established just from the combinatorics of the collection of their supports. To exhibit such a family you also have some hints above. You then have a couple of topological proofs, that also come from more general facts: (I) no complete metric topological linear space has countable dimension, and (II) non-separable topological linear spaces have uncountable dimension. A Hilbert space proof is also available, using the isomorphism of $\ell ^{2}$ with $L^{2}$, where the uncountable dimension is more evident. Finally, a simple linearly independent uncountable family is given by exponential sequences; to show the independence you have an asymptotic order argument and a purely algebraic proof. In fact, it is now clear that you can make a proof out of virtually any result vaguely linked with the topic. --pma (talk) 12:33, 27 September 2009 (UTC)

Convergence of random variables in mean

Is there a simple example of a sequence of random variables that converge in mean to some random variable or constant, but don't converge in mean square? 128.237.235.59 (talk) 19:57, 25 September 2009 (UTC)

Take $\Omega =[0,1]$ with the Lebesgue measure, and $f_{n}:=a_{n}\chi _{[0,1/n]}$, where $\chi _{[0,1/n]}$ is the characteristic function of [0,1/n]. Choose conveniently the coefficients $a_{n}$. --pma (talk) 23:41, 25 September 2009 (UTC)