15,516 reputation
44276
bio website thenerdiestshirts.com
location
age
visits member for 4 years, 3 months
seen 7 hours ago

12h
comment Probability of differently loaded dice summing to a value
Once again, dynamic programming does not mean "generating every set of integers that can be summed to equal some constant." Perhaps you should look it up again and try to implement it. en.wikipedia.org/wiki/Dynamic_programming It's like multiplying polynomials. It is not an exponential exhaustion of combinations.
16h
comment Probability of differently loaded dice summing to a value
Dynamic programming does not mean "generate every term." It should be extremely fast if you only need to do this millions of times. If it isn't fast enough, then you should explain what other features of the problem prevent it from being fast enough. You can use something like a normal approximation in some circumstances, but then you have to worry about the error. Why not use a direct calculation? Anyway, it seems like there isn't any research level component of this question, so I'm voting to close. If you are having trouble implementing dynamic programming try Stack Overflow.
18h
comment Probability of differently loaded dice summing to a value
Are all of the values on the dice integers? If so, dynamic programming should be fast. Recursively compute the probability distribution for the sum of the first $k$ dice. If that doesn't work you should say why not, and explain the structure of the problem more clearly. For example, you say you have to do this millions of times. What is different and what is the same between different computations?
2d
comment What is the best lower bound for 3-sunflowers?
I checked a construction in math.uiuc.edu/~kostochk/docs/old/jcta97degm.pdf which has a non-uniform $3$-free family of $388$ sets of average size $3404/388$. The non-uniformity doesn't matter much since after taking a large power, you can select a uniform subfamily which is almost as large. Unfortunately that gives a worse bound ($388^{388/3404} = 1.97$), but they were trying to optimize something slightly different.
2d
comment What is the best lower bound for 3-sunflowers?
One easy lower bound comes from taking one side from each of $a$ disjoint pentagons. This gives $5^a$ sets of size $2a$ with no sunflower of size $3$, so $C_3 \ge \sqrt{5}$. I recall that someone showed me a better construction a couple of decades ago involving the Petersen graph but I don't recall the details.
Apr
14
comment Limit of distance between two random points in a unit $n$-cube
One way to see that the answer is $\infty$ is that with high probability, about $n/4$ of the coordinates will differ by at least $1/2$.
Apr
12
comment Probability all inner products are zero
@Anush: The indicators you mention are $1$ with probability ${n \choose n/2}/2^n$ (for $n$ even, of course). I don't know the probability that $I_iI_j=1$ but it should depend on $\textrm{GCD}(i-j,n)$. If $\vec v$ must satisfy $v_k = v_{k+n}$ then the probability $I_iI_j=1$ should be computable. I think there is generally a positive correlation since the probability of a larger product being $1$ is greater than the product of the probabilities.
Apr
8
comment Probability all inner products are zero
Given $\vec u$, there is an $n-1 \times n-1$ matrix associated to it which sends $(a_1,...a_{n-1}) \mapsto (a_2,...,a_n)$ so that $(a_1,...,a_n) \perp \vec u$. This matrix has a fairly simple form, particularly if you assume (without loss of generality) that the last entry of $\vec u$ is $-1$. It is a companion matrix of a polynomial with all $\pm 1$ coefficients. However, I haven't been able to establish periodicity using this matrix.
Apr
8
comment Probability all inner products are zero
Here are some values of $(n,\textrm{count})$. All of the long vectors were symmetric by translation by $n$ although I haven't proved that this is necessary. $(2,8)$, $(4,40)$, $(6,224)$, $(8,1064)$, $(10,3808)$, $(12,21280)$, $(14,59200)$, $(16,322600)$, $(18,1166624)$. The last took $25$ minutes of computing time, and $n=20$ would take about $8$ hours.
Apr
7
comment A strengthening of Frankl's union-closed conjecture?
For other parameters, every element is in the set, since there is an injection from sets not containing $x$ to sets containing $x$ by adding $x$.
Apr
7
comment A strengthening of Frankl's union-closed conjecture?
I think you mean $\ge k$. If so, then for $k=3, n=4$ this is not an example. $4 \in \lbrace 1,2,3,4 \rbrace,\lbrace 1,2,4 \rbrace, \lbrace 1,3,4\rbrace, \lbrace 2,3,4\rbrace$ so $4$ is in $4$ out of $7$ sets. $1$ and $3$ are in $5$ out of $7$. $2$ is in $6$ out of $7$.
Apr
6
comment Combinatorial design for minimization problem over binary strings
@Fei Gao: Perhaps people are mixing up first and last. That the first $0$ is in the first position does not mean the cost is $0$. The cost of $01111101$ is $5$, since there are $5$ $1$s before the last $0$, even though there are no $1$s before the first $0$.
Apr
5
comment Combinatorial design for minimization problem over binary strings
@The Masked Avenger: Consider the images of $11111001$: itself and $11111010$ and $11111100$. These have costs of $5$, $6$, and $6$, for a minimum of $5$. To get a low cost, you need to move both $0$s close to the beginning.
Apr
3
comment Probability all inner products are zero
There are just as many possibilities where the short vector is all $1$s as all $-1$s, or where the long vector is all $1$s, or all $-1$s.
Apr
3
comment Number of lattice polytopes contained in a given lattice polytope?
It's easy to modify Per Alexandersson's suggestion so that the polytopes are the same dimension. If there are $n$ vertices of a convex hull, and some tetrahedron $T$ contained in the interior, then a subset of the vertices $S$ is determined by the convex hull of $S\cup T$, so there are at least $2^n$.
Apr
3
comment Base-signed harmonic series
It looks like you copied a lot from my question mathematica.stackexchange.com/questions/45160/…. Even though you are not asking the same question I think you should have provided a reference.
Apr
2
comment Is it possible to determine if these random numbers are not really random?
See en.wikipedia.org/wiki/Randomness_tests. Also, try math.stackexchange.com for general mathematics questions.
Mar
31
revised Convergence of a sequence of dependent binomial trials
Added Poisson limit.
Mar
30
comment Are there nontrivial real functions of 2 real variables with gradient having constant euclidian norm on each level line?
The distance to a nonempty set doesn't have continuous partial derivatives. $(x,y) \mapsto ax+by$ does.
Mar
30
comment Convergence of a sequence of dependent binomial trials
@JoelO: Yes, I'm working on an edit. Variance bounds give you better results when $b_0$ is $o(n)$. The probability that $b_t$ is large can't be too high because it is a martingale and the average stays the same.