# Tag Info

5

A recent paper by Vigna starts with an explanation of the history of Mersenne-Twister (MT), and why it has prevailed so far. The original paper about the Mersenne Twister was published by Makoto Matsumoto and Takuji Nishimura in 1997 [22]. At that time, the PRNG had several interesting properties. In particular, it was easy to build generators with a very ...

3

Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible. Proof (perhaps slightly informal): Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows ...

2

Yes, all you have to do is to uniformly sample a simplex, and then sort the elements, under the assumption that the given distribution on the simplex is invariant under the permutation of the coordinates and the probability of a 0-measure set is 0. That assumption holds often by default. Hopefully it holds in your situation. otherwise, a different sampling ...

2

One standard approach is to use inverse transform sampling: if $F$ is the cdf of the desired random variable and $U$ is uniformly distributed, then $F^{-1}(U)$ has the desired distribution. There are more sophisticated methods for specific distributions; you can find references and links where you can learn more in the linked Wikipedia article.

2

Yes actually, and it's quite simple. Sample a random integer $q$ from $[n-k]$. Initialize $c = |\{x \in S \mid x \leq q\}|$. While $c > 0$, let $q \leftarrow q + 1$ and if $q \notin S$ decrement $c$. Return $q$. This works because steps 2 and 3 forms a bijective mapping from $[n -k]$ to $[n] \setminus S$. Finally the algorithm runs in $O(k)$ because it'...

1

This is exactly what the A-Res algorithm is for If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time. The way you achieve this is: For each sample: randomly generate a number between from 0 to 1 Raise the result to the power of ...

1

There is no particular downside. It's a perfectly valid approach.

1

I have a suggestion for an algorithm that might get close to what you want: Pick $m$ from the distribution $\mu$ (which I will describe below). Choose $S$ uniformly at random from all sets containing exactly $k-1$ integers in $[m+1,\dots,\min(m+w,n))$. Add $m$ to $S$. Output $S$. So, how do we pick the distribution $\mu$ to make this algorithm pretty ...

1

Let $l$ be the number of distinct characters in the input string. So our input size is summarized by $n, k, l$, with $k \le n$ and $l \le n$. Here is one efficient way to do it. In the first step, since the order of characters in the string doesn't matter, let's turn it into a map: $$M = \{a \mapsto 1, d \mapsto 3, y \mapsto 1\}.$$ The idea of our ...

1

The problem of generating random $d$-regular graphs uniformly at random has been extensively studied. Some of the proposed algorithms are quite sophisticated. In general, the problem becomes more difficult as $d$ grows as a function of $n$. To the best of my knowledge, the problem is still open for $d = \omega\left(\sqrt{n}\right)$. However, if one assumes ...

Only top voted, non community-wiki answers of a minimum length are eligible