5,478 reputation
52039
bio website
location California
age
visits member for 3 years, 2 months
seen 10 hours ago

A mediocre professor at a top-notch university making mediocre contributions to this top-notch community


Aug
5
comment Expected length of a sequence that contains all words of a given length.
@ByronSchmuland I think that's the same ref leonbloy cited at the end of his answer below.
Aug
4
comment N white and black balls and N boxes Probability
Given $N$ new users posting $N$ new questions which are worded as demands rather than questions, what is the probability they are all homework problems?
Jun
29
comment on fibonacci sequence how to prove that $a_n=\frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$
This is given as a warmup in the free text by Wilf called generatingfunctionology.
Jun
28
comment How to find generator in a finite group?what is generator?
When I said, "suppose you can factor" the "you" is the OP who is (presumably) a human trying to solve a problem. I did not (and would not) say "suppose a factorization exists for $(p-1)$".
Jun
24
comment practical arithmetic in prime factorizations
Ross, I don't get your answer. You seem to be reiterating his idea rather than answering his question regarding the use of this technique in actual software.
Jun
15
comment How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$?
@PeterR: Often mathematicians will use "elementary" to mean "does not use complex analysis". As you can see, "elementary" does not mean "easy."
Jun
15
comment Conjecture: The following sum is asymptotic to $\sqrt{9πm/8}$
Interesting. This immediately gives that three collisions occur in less than an expected $2 \sqrt{\pi m/2} = \sqrt{2\pi m}$. (In fact, I will guess that it's $15/8 \sqrt{\pi m/2}$.) Since $\sqrt{2\pi m}$ is the square root of the circumference of a circle of radius $m$, there is clearly a geometric proof we're missing. :)
Jun
15
comment How many even number in a sequence are there?
Your iff is false in both directions.
Jun
15
comment Second pair of matching birthdays
@ShreevatsaR: The reason my simulation made me believe the answer was not proportional to $\sqrt{M}$ was that--as your program shows--the multiplier starts above 2.1 and gradually settles to 1.88... But your argument in your answer that it must be a multiple of $\sqrt{M}$ is quite convincing.
Jun
15
comment How many expected people needed until 3 share a birthday?
Following the link to your other question, and then to the Sedgewick/Flajolet book, and then a reference from there, I found a paper that gives the derivation for this result: sciencedirect.com/science/article/pii/S0021980067800759
Jun
15
comment How many expected people needed until 3 share a birthday?
Thanks, Byron. I had guessed that $E(T) \approx c M^{2/3}$, but simulations I ran showed $c$ growing slightly with $M$ so I thought the $2/3$ exponent was a tad low. It could instead be the effect of lower-order terms in the asymptotics.
Jun
15
comment How many expected people needed until 3 share a birthday?
I am asking for the expected number of balls where a 3-way collision occurs. But I would be happy to learn the "median" value, which is the number of balls where the a 3-way collision has probability $\approx$ 1/2.
Jun
14
comment Second pair of matching birthdays
I have worked (unsuccessfully) at finding a closed form for the constant $c \approx 1.88$ that you approximate via your python program above. Unfortunately the integral that so nicely turns into $\sqrt{\pi/2}$ ends up being much harder with the ${n \choose 2}$ multiplier.
Jun
10
comment Prove that if $n$ is a composite and $p \gt \sqrt[3]n$, then $n/p$ is a prime.
If you look at the edit history, it used to say "composite" at the time my response was offered.
Jun
1
comment Second pair of matching birthdays
Very nice! I have been working on this problem since I posted it and I followed virtually the exact same steps as you do above, but you are faster. I just last night wrote the same program you did (in C instead of Python, but they're almost identical!). I feel guilty seeing all the work you did on this... I'm doing this just for fun (it's summer after all!). Cheers.
Jun
1
comment Second pair of matching birthdays
Well, I mostly understand what you did, but you approximated the median (tosses needed to get a 50% probability) rather than the mean, and they are not asymptotically equal for this problem (as you point out). Based on computer simulations I've run, your 55% estimate isn't quite right: for small $M$ we need about 60% more, and for larger $M$ (say 100,000) it's less than 50%. I don't think this 2-collision mean is proportional to $\sqrt{M}$ like the 1-collision mean is.
May
31
comment Second pair of matching birthdays
I agree with you that this is the probability of obtaining 2 (or more) collisions throwing $n$ balls into $M$ bins, but I was asking for an expectation. Every technique I know of requires computing a sum.
May
31
comment Second pair of matching birthdays
My statement is "ball lands in an occupied bin" twice; that would encompass both or your scenarios. (Restricting to either of your two sub-cases would be interesting problems as well... I would be happy to see a solution to any of them.)
Apr
24
comment Expected length of a sequence that contains all words of a given length.
I know I'm getting old when a related question was asked by me and I have no memory of asking it.
Apr
21
comment Prove or disprove isomorphic graphs
It should be classified as "group theory" instead of "graph theory." Even if this problem came from graph theory, your presentation of it leaves no trace of that evolution and you've given it as a pure group theory problem.