Alex R.
Reputation
2,214
Next privilege 2,500 Rep.
Create tag synonyms
 Oct 24 awarded Good Answer Oct 21 awarded Yearling Sep 15 comment “Most Similar Vector Problem” on an Integer Lattice? @BerkU.: it should be the global best solution because the global solution must be located at one of the shaded box corners (you will have to check in the negative direction as well). Sep 12 awarded Good Answer Aug 2 answered “Most Similar Vector Problem” on an Integer Lattice? Aug 2 comment “Most Similar Vector Problem” on an Integer Lattice? Curiously, why isn't this solvable by zig-zagging the lattice? For example if $n=2$, of the four points on the unit square, pick the closest to your vector. Lets say this point is $(1,1)$, in the positive quadrant. Look one step up and right and determine which location is closer to $u$. Move to that point, and repeat. Collect all distances this way, and pick the minimum one. You might have to repeat this with the initial best point in the opposite quadrant to check the other direction. It seems like this algorithm is $O(Mn)$. Or just find all unit boxes $u$ intersects and poll each vertex. Jul 11 comment Which subgroup order of the symmetric group is the most frequent? @EricWofsey: It seems like a difficult question actually, see the top answer here: math.stackexchange.com/questions/76176/… Jul 9 comment Another name for coin-flipping polynomials They are homogenous polynomials for each $n$ in variables $x,y=(1-x)$ I'm not sure what else you can say without making some kind of restrictions. Jul 9 comment Another name for coin-flipping polynomials A general singleton has probability $x^k(1-x)^{n-k}$ in the coin space. Any event is thus $\sum_{k\in E}x^k(1-x)^{n-k}$, where $E$ is an index multiset set of the event, which is the form of the most general coin polynomial. Jul 5 comment Distribution of trivial subset sums If you add $L+1$ to the interval, then you're looking at the number of ways to sum to $L+1$ from $[1,L]$. You necessarily need all your chosen numbers to be less than $L-1$, which occurs with probability $\binom{L-1}{n}$, after which you are evaluating $p(L-1)$: the number of partitions of $L-1$ with distinct parts, which equals the number of partitions with odd parts by Euler's theorem. I'm guessing the growth rate is known via circle methods or other analytic combinatorics, probably something like $O(\exp(c\sqrt{n})/n)$. Jun 25 comment Logarithmic integral, $π(x)$ and $x/(\ln x)$ Not yet. See the discussion here: en.wikipedia.org/wiki/Skewes'_number#More_recent_estimates Jun 25 comment Extrapolation between longest increasing and longest alternating subsequences A trivial observation: there's some strange parity here. The Tracy widom distribution is biased toward one side, whereas the Gaussian is symmetric about the mean. This is evident here since for small $m$, we basically have reflection symmetry. So I would expect the transition to occur when $m\gg n/2$. Jun 23 comment Semicircle law universality elsewhere thanks for all your answers! Jun 23 comment Bounds on the probability of k-of-n events in terms of bounds on single and pairwise probabilities It sounds like you could really use something akin to positive/negative association such as $P(A_i\cap A_j)\leq \geq P(A_i)P(A_j)$. Do you happen to know if these hold on some large subset of index pairs? Jun 22 revised Semicircle law universality elsewhere added 4 characters in body Jun 22 comment Why is this distribution exponential? Try working this out with just two points. Jun 22 comment Why is this distribution exponential? Basically by rescaling the interval as a function of $n$ the waiting time between successive points becomes a poisson process. This is because the probability of seeing the next point is proportional to the interval you are looking at. Jun 19 comment Semicircle law universality elsewhere @jon bannon: I'm not intimately familiar with it but I basically lumped it with random matrix theory. If this is wrong of me I would love to see a note on this. Jun 19 revised Semicircle law universality elsewhere deleted 1 character in body Jun 19 asked Semicircle law universality elsewhere