Timeline for Bounding the probability of success of adding elements into a list
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 5, 2020 at 16:05 | history | bounty ended | CommunityBot | ||
| S Nov 5, 2020 at 16:05 | history | notice removed | CommunityBot | ||
| Nov 2, 2020 at 15:16 | comment | added | user1246462 | Thanks for the comment! That's a very important part of the question that I accidentally left out in the revision. All elements are hashed using the same hash function and M_i is the X smallest elements of L_i by hash value. I've updated the question with this info. Notably this means that C and M_i are correlated. | |
| Nov 2, 2020 at 15:10 | history | edited | user1246462 | CC BY-SA 4.0 |
added 265 characters in body
|
| Nov 2, 2020 at 12:32 | comment | added | RaphaelB4 | What are the random laws in your problem? $L_1,\cdots,L_k,M_1,\cdots,M_k,C_i$ are random ? | |
| Nov 1, 2020 at 15:42 | history | edited | user1246462 | CC BY-SA 4.0 |
added 78 characters in body
|
| S Oct 28, 2020 at 14:46 | history | bounty started | user1246462 | ||
| S Oct 28, 2020 at 14:46 | history | notice added | user1246462 | Draw attention | |
| Oct 27, 2020 at 20:24 | history | edited | user1246462 | CC BY-SA 4.0 |
deleted 1086 characters in body
|
| Oct 27, 2020 at 2:07 | comment | added | user1246462 | @MattF. No this doesn't miss anything. I would just add that we want to minimize the value of $X$. Feel free to update the question with this formulation. Otherwise I will update it tomorrow. | |
| Oct 26, 2020 at 22:05 | comment | added | user44143 | Does this shorter version miss anything essential, and if so why is the missing bit essential? Suppose $L_1, \dots, L_k$ are lists with $n$ elements each, and $M_1, \dots, M_k$ are sublists with the smallest $X$ elements in each list. Let $C_1$ contain some elements from the lists. Define more $C$'s by: if $|C_i \cap M_i| < X/r$, let $C_{i+1} = C_i \cup L_i$; and otherwise let $C_{i+1} = C_i$. What size of $X$ will ensure with probability at least $1 - 1/n^2$ that: If $|C_i \cap M_i| < X/r$, then $|C_i \cap L_i| < 1.1 n/r$; and otherwise, $|C_i \cap L_i| > 0.9 n/r$? | |
| Oct 26, 2020 at 20:49 | comment | added | user1246462 | Thanks, I edited the problem statement such that $c$ is gone and $\epsilon$ is some error bound that you can determine (instead of a parameter that is an input to the problem). | |
| Oct 26, 2020 at 20:48 | history | edited | user1246462 | CC BY-SA 4.0 |
added 82 characters in body
|
| Oct 26, 2020 at 15:33 | comment | added | user44143 | So $X$ can depend on $n$, $r$, $c$ and $\epsilon$? That's a lot of variables. It would be easier to understand with a more concrete version of the problem where two of them are fixed, if you can find parameters that still give an interesting version of the problem. | |
| Oct 26, 2020 at 14:58 | history | edited | user1246462 |
[Edit removed during grace period]
|
|
| Oct 25, 2020 at 5:30 | history | asked | user1246462 | CC BY-SA 4.0 |