22,086 reputation
33761
bio website
location
age
visits member for 3 years, 8 months
seen 22 mins ago

?


Apr
7
comment Which one result in mathematics has surprised you the most?
@KCd: But perhaps it was a surprise that there was such a simple algorithm and proof -- note that the Riemann hypothesis, generalized or not, seems still very far from solution. (That's what the answer seems to be saying.)
Apr
6
comment How many times does a single fair die have to be rolled for a number to repeat
@CarlGerman: No, the geometric distribution is the number of times you must roll dice before you see a particular number (say $4$). (Or more generally, number of independent trials until some event.) It is a very different sort of distribution, and it does not have bounded support: you might be staggeringly unlucky and need arbitrarily many dice throws before seeing that particular event. I'm not aware of any standard name for this distribution here, but the formula is the same as that for the birthday problem.
Apr
6
comment Probability that a random graph is planar
@JackD'Aurizio: Just for completeness, that turns out to be sufficient to prove the claim: $\dfrac{2^{9n \log n}}{2^{n(n-1)/2}} = 2^{9n\log n - n(n-1)/2}$, and so we want to say that $9n\log n - n(n-1)/2 < -0.49n^2$ or that $9n\log n < n(n-1)/2 - 0.49n^2 = 0.01n^2 - n/2$ for sufficiently large $n$. And this is clearly the case, as the LHS grows as $\Theta(n \log n)$ but the RHS as $\Theta(n^2)$.
Apr
6
comment Find the probability generating function
@vonbrand: Why not? $X$ and $Y$ are independent, therefore so are $u^{2X}$ and $u^{2Y}$. In fact, that you can multiply expected values (of independent random variables) is AFAIK one of the main reasons for using probability/moment generating functions in the first place. :-)
Apr
6
comment Generating functions for compositions
We can also prove $g(n) = h(n-1)$ for $n \ge 1$ by noticing that $$\sum_{n \ge 1}h(n-1)z^n = zH(z) = \frac{z}{1-z-z^2}=\frac{1-z^2-(1-z-z^2)}{1-z-z^2} = G(z) - 1 = \sum_{n\ge 1}g(n)z^n$$
Apr
6
comment Generating functions for compositions
+1. But note that: (A) your generating function $\frac{z}{1-z-z^2}=z+z^2+2z^3+\dots$. But arguably it makes sense to say $g(0)=1$ (for the empty composition), which gives the GF $\frac{z}{1-z-z^2}+1=\frac{1-z^2}{1-z-z^2}$ as in my answer. Similarly, $\frac{z+z^2}{1-z-z^2}=z+2z^2+3z^3+\dots$, and adding $h(0)=1$ gives $\frac{z+z^2}{1-z-z^2}+1=\frac{1}{1-z-z^2}$. Allowing the zero values lets us say that $g(n)=h(n-1)$ for $n\ge1$ instead of only $n\ge2$. (B) We can argue directly from GFs instead of using facts about Fibonacci numbers: in your notation, we have $zH(z)=G(z)+z$, which proves it.
Apr
6
answered Generating functions for compositions
Apr
6
comment How many times does a single fair die have to be rolled for a number to repeat
@CarlGerman: I've added it to the answer.
Apr
6
revised How many times does a single fair die have to be rolled for a number to repeat
fix bug, include calcluation
Apr
6
comment How many times does a single fair die have to be rolled for a number to repeat
@CarlGerman: For $n=6$, doing this calculation gives expected value $E[k+1] = \frac{1223}{324} \approx 3.77$.
Apr
6
comment How many times does a single fair die have to be rolled for a number to repeat
@CarlGerman: putting two numbers together, as in $\frac{5}{6}\frac{4}{6}$, just means multiplying them; I realise it might have been confusing because I used $\cdot$ as well for the same purpose (I just used the latter to make the last one stand out). The general formula for dice with $n$ faces (numbered $1$ to $n$) is that the repeat happens after $k+1$ rolls (where $k \ge 1$) with probability $$\frac{n}{n}\frac{n-1}{n}\frac{n-2}{n}\cdots\frac{n-k+1}{n} \frac{k}{n} = \frac{n!k}{(n-k)!n^{k+1}}.$$
Apr
5
comment Visually stunning math concepts which are easy to explain
That the circle's perimeter is $2\pi r$ is the definition of $\pi$, so I wouldn't say this is an explanation of the fact; rather it's an illustration of what the definition means, and that the value of $\pi$ is about $3.1$.
Apr
5
comment Visually stunning math concepts which are easy to explain
I don't understand what this is showing: is it showing hte approximation of a square wave by a Fourier series?
Apr
5
comment Compute a sum with partial fraction decomposition and generating functions
Just for completeness: $\sum_{n=1}^{\infty} H_n z^n = \sum_{n=1}^{\infty} (\sum_{k=1}^n \frac1k) z^n = \sum_{k=1}^{\infty} \frac1k \sum_{n=k}^{\infty} z^n = \sum_{k=1}^{\infty} \frac1k \frac{z^k}{1-z} = \frac{1}{1-z} \sum_{k=1}^{\infty} \frac{z^k}{k} = \frac{1}{1-z}\ln\frac{1}{1-z}$, if I've not made any mistake. So its square is $\frac{1}{(1-z)^2}\left(\ln\frac{1}{1-z}\right)^2$, but it's not clear how to get $a_n$ from that (except by solving the original problem).
Apr
4
comment Is an SD card a fair coin… to me?
@BenVoigt: The comment must at least tangentially attempt to address the question. The question here is about philosophy / interpretation of probability -- the OP explicitly discounts the effect of further information, like a design engineer knowing the physics of the card. On top of that, this "answer" is a factoid about coins, and it does not appear from the paper that it applies to an object like an SD card. Even if it did, this is like answering, say, a combinatorics question about counting seating arrangements with some trivia that sidesteps the question. :-)
Apr
4
comment Generating functions for compositions
Can you write down the generating functions for the case when there are no restrictions on the compositions?
Apr
3
comment Is an SD card a fair coin… to me?
@JackM: The question is what you know before flipping it. What probabilities should you assign, based on your (no) knowledge, before you have any information from flipping it? The OP has already discounted the case where you already have some knowledge (e.g. from its design), let alone from flipping it 1000 times.
Apr
3
comment How many times does a single fair die have to be rolled for a number to repeat
@CarlGerman: If that's not clear, I can try to explain again differently.
Apr
3
comment How many times does a single fair die have to be rolled for a number to repeat
@CarlGerman: Different dice rolls are independent, so the probability of an outcome in some dice roll is the same whether or not we condition it on outcomes in other dice rolls. For the pattern $aba$, the probability of getting $a$ on the first dice roll is $1$ (because whatever the first dice roll is, that's what we call $a$); the probability of getting a $b$ different from $a$ on the second dice roll is $\dfrac{5}{6}$ (because there are $5$ possible choices of $b$ different from $a$); and probability of getting either $a$ or $b$ on the third roll is $\dfrac{2}{6}$ (two choices out of six).
Apr
2
comment Is an SD card a fair coin… to me?
@soakley: I think he originally wanted to flip a fair coin, but he must have figured it out long ago (possibly by getting an actual coin) — the question actually asked here is about how we can know whether something is fair.