Skip to main content
21 events
when toggle format what by license comment
Apr 13, 2017 at 12:19 history edited CommunityBot
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Jul 19, 2012 at 17:30 vote accept Raphael
Jul 14, 2012 at 10:21 answer added Douglas Zare timeline score: 2
Jul 13, 2012 at 23:51 history edited Raphael CC BY-SA 3.0
added 7 characters in body
Jul 13, 2012 at 23:43 history edited Raphael CC BY-SA 3.0
added 100 characters in body; added 79 characters in body
Jul 13, 2012 at 23:42 comment added Douglas Zare A universal lower bound like that is easy: The expected number of duplicates among the first $m$ is an upper bound for the probability of a duplicate in the first $m$. For $m = c \sqrt{n}$ and $k\ge 2$, the expected number of duplicates is under $c/2$, so the probability that the first duplicate is greater than $\sqrt{n}$ is greater than $1/2$, which means the expected first duplicate is greater than $\sqrt{n}/2$.
Jul 13, 2012 at 23:41 comment added Raphael @Douglas Zare, right. I will clarify the post.
Jul 13, 2012 at 23:32 comment added Douglas Zare I was talking about lower bounds for the maximum over all $k$-independent processes. I guess you are talking about uniform lower bounds for all $k$-independent processes instead. I haven't thought about that.
Jul 13, 2012 at 23:31 comment added Raphael Maybe we are using the term "lower bound" in different ways. I mean the following. Fix a k, what is the highest lower bound that applies for all k-independent processes. For k=1 (which was excluded as an example in my original question), it is $2$. For $k \geq 2$, I suspect it is $\Omega(\sqrt{n})$ but don't know how to show it.
Jul 13, 2012 at 23:25 comment added Raphael @Douglas Zare, I don't understand. As an extreme case, take a $1$-independent process that picks the first value uniformly at random and then sets every other sample to be the first value chosen. This is has mean time to find a duplicate of $2$ which is lower than the lower bound for full independence.
Jul 13, 2012 at 21:59 comment added Douglas Zare Independence implies $k$-independence. So, take a construction where the expected time is $\Omega(\sqrt{n})$ and the variables are independent, and this is automatically a lower bound for $k$-independent for any $k$.
Jul 13, 2012 at 21:19 comment added Raphael @Douglas Zare, How do you show this is also a lower bound under $k$-independence?
Jul 13, 2012 at 20:55 comment added Douglas Zare Under independence, the expected time until the first duplicate is already $\Omega(\sqrt{n})$.
Jul 13, 2012 at 18:40 comment added Raphael @Douglas Zare, That would be very interesting as it would imply that there is a dramatic difference between $2$ and $4$-independence. Does this approach have any chance of showing an $\Omega(\sqrt{n})$ lower bound as well?
Jul 13, 2012 at 18:24 comment added Douglas Zare That blog covered part of the calculations I did. Chebyshev's inequality is usually far from sharp, and perhaps replacing it with something stronger would provide slightly better estimates on the probability that there are no duplicates among the first $m$, which may be enough to prove $O(\sqrt{n})$.
Jul 13, 2012 at 17:37 history edited Raphael CC BY-SA 3.0
deleted 58 characters in body
Jul 13, 2012 at 17:13 history edited Raphael CC BY-SA 3.0
added 231 characters in body; edited tags
Jul 13, 2012 at 17:10 comment added Raphael @Douglas Zare, blog.computationalcomplexity.org/2009/11/… has a related bound using the 2nd moment when $k=4$. I will a reference request to the question too as maybe someone has worked on this before.
Jul 13, 2012 at 1:42 comment added Douglas Zare If $k \ge 4$ then you can compute the second moment of the number of duplicates among the first $m$. The Chebyshev inequality is not quite good enough to give $O(\sqrt{n})$ from this.
Jul 12, 2012 at 23:35 history edited Raphael CC BY-SA 3.0
added 34 characters in body; deleted 9 characters in body
Jul 12, 2012 at 23:30 history asked Raphael CC BY-SA 3.0