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
