29

What you can do, is to employ a method called rejection sampling: Flip the coin 3 times and interpret each flip as a bit (0 or 1). Concatenate the 3 bits, giving a binary number in $[0,7]$. If the number is in $[1,6]$, take it as a die roll. Otherwise, i.e. if the result is $0$ or $7$, repeat the flips. Since $\frac 68$ of the possible outcomes lead to ...


26

Let us first assume that you want to sample within x + y + z = 1 0 ≤ x ≤ 1 0 ≤ y ≤ 1 0 ≤ z ≤ 1 This doesn't make quite a difference, since the sample point will still lie in your requested area with high probability. Now you are left with sampling a point from a simplex. In the 3d example you get a 2d simplex (triangle) realized in 3d. How to pick a ...


15

MT was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs. The table at pcg-random.org e.g. gives a good overview of features of some of the most used PRNGs, where the only "good" feature of the Mersenne Twister is the huge period, $2^{219937}$ and the possibility to use a ...


14

A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random. Many methods for shuffling seem uniform to people but are not and so it is ...


13

Yes and no, depending on what you mean by “the only way”. Yes, in that there is no method that is guaranteed to terminate, the best you can do (for generic values of $N$ and $R$) is an algorithm that terminates with probability 1. No, in that you can make the “waste” as small as you like. Why guaranteed termination is impossible in general Suppose that you ...


12

Binary trees are counted by Catalan numbers: the number of "full" binary trees (each node has either 0 or 2 children) with $n$ leaves is $C_{n-1}$. The Catalan numbers are given by an explicit formula, and also satisfy the recurrence $$ C_{n+1} = \sum_{i+j = n} C_i C_j, $$ which follows directly from the interpretation as counting binary trees. You can use ...


12

To have a slightly more efficient method than the one pointed out by @FrankW but using the same idea, you can flip your coin $n$ times to get a number below $2^n$. Then interpret this as a batch of $m$ die flips, where $m$ is the largest number so that $6^m < 2^n$ (as already said, equality never holds here). If you get a number greater or equal to $6^m$ ...


11

The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/...


9

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth. Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so ...


9

Triangulate the polygon Determine in which of the triangles the point should lie (weights triangle areas) Sample the point in the triangle as explained in this post


9

There is a simple $O(n)$ algorithm using the technique of reservoir sampling. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero, put it in $x$ with probability $1/m$. You can show (exercise) that the final contents of $x$ is a uniformly random zero from the file. If you are allowed ...


8

There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs. Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform ...


8

Regardless of the algorithm you use, if you have $i$ bits of random data, you can generate a maximum of $2^i$ possible permutations. If $i$ is smaller than $log_2(n!)$, then there will be some permutations which cannot be produced, and you will have, in effect, decided which permutations those are when you encode your algorithm. (You may not be able to ...


7

This is to add to the existing answers. Devroye is an excellent reference for questions of this sort. Chap.7 gives the algorithms needed to generate uniform order statistics, which the OP is after. For generating uniform order statistics, sorting $n$ samples of $[0,1]$ will do. This approach takes $O(n \log n)$ time. A quicker way ( available in the book) ...


7

An alternative to rejection sampling (as described in FrankW's answer) is to use a scaling algorithm, that takes into account an answer of [7,8] as if it was another coin flipping. There is a very detailed explanation at mathforum.org, including the algorithm (its NextBit() would be flipping your fair coin). The case for throwing a dice with a fair coin (...


7

The short answer is that you can't use that software as-is to get what you want. For a fixed $m$, the Barabasi-Albert model always has the degree distribution $P_k \sim k^{-3}$, regardless of $m$. The exact formula for the probability degree of what those pieces of software implement (which is the BA model) is $$ P_k = \frac{2m(m+1)}{k(k+1)(k+2)}$$ The ...


7

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal distribution with mean $np$ and standard deviation $\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to $np$ with high probability. When $p=c/n$ for fixed $c$,...


7

As Andrej explains in his answer, a random shuffle consists of applying a uniformly random permutation on the input, or equivalent. Your algorithm, in contrast, applies $n$ random transpositions. This cannot possible produce an exact random shuffle, since the probability of each resulting permutation is of the form $A/n^{2n}$, which cannot equal $1/n!$. ...


7

I am the Editor who accepted the MT paper in ACM TOMS back in 1998 and I am also the designer of TestU01. I do not use MT, but mostly MRG32k3a, MRG31k3p, and LRSR113. To know more about these, about MT, and about what else there is, you can look at the following papers: F. Panneton, P. L'Ecuyer, and M. Matsumoto, ``Improved Long-Period Generators Based on ...


7

The algorithm works just fine. Note that each node's size field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm just going to assume that a child's size is zero if the child is null. Thus, for any node in the tree, we have this.size == left.size + 1 + right.size Consider the root of the tree. If we ...


6

Shannon's source coding theorem shows that, in some exact sense, you need $\log N/\log R$ samples (on average) of the type $[0,\ldots,R-1]$ to generate a random number of the type $[0,\ldots,N-1]$. More accurately, Shannon gives an (inefficient) algorithm that given $m$ samples of the first type, outputs $m(\log N/\log R - \epsilon)$ samples of the second ...


6

I am not 100% sure this answer is correct, but here goes: I think you can reduce this to uniformly random any-paths, from $s-t$, in a DAG with a single source and a single sink. Given a graph $G$ Make a new empty digraph, $H$. First: run the BFS part of Dijkstra's shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$. ...


6

It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic algorithms) being only one of them. That said, I have a positive answer and a negative answer for you. Positive answer. Consider the problem of maximizing a ...


6

It appears to be a random geometric graph. Points are placed at random within an area, according to some distribution, and an edge is added between every pair of points whose distance is less than some threshold. A common case is to distribute the points uniformly at random within the unit square and add edges between all pairs of vertices that are at ...


6

No, there is no algorithm that shuffles an array of length $n > 2$ using a bounded number of random Booleans. This is because given an algorithm that uses $m$ random bits (at most), each outcome has a probability of the form $A/2^m$, whereas we need each possible permutation to have probability $1/n!$. When you're using Fisher–Yates shuffle in the form ...


5

This problem is covered in The Art of Computer Programming. I can't recall exactly where, but the algorithm is pretty easy to understand when you know the trick. Let $l$ be the number of lines read so far. At each stage, you read the next line from stdin. Choose $r$ to be a random integer uniformly chosen from the range $[1,l+1]$. If $r \le k$, then discard ...


5

Here is a solution based upon the ideas in Realz Slaw's answer. It is basically a re-exposition of his ideas that might be clearer or easier to follow. The plan is that we will proceed in two steps: First, we will build a graph $S$ with the following property: any path from $s$ to $t$ in $S$ is a shortest path from $s$ to $t$ in $G$, and every shortest ...


5

Actually, no, rejection sampling is far from the only way of proceeding. Unfortunately, considering that computers store all information as bits, and thus can only manipulate random bits of information, any algorithm to draw a uniform random variable of range $N$ will be infinite, if the binary base development of $N$ is infinite. This theorem is a ...


5

There are no general algorithms for your problem but what one usually does (for graphs of small orders) is Use nauty to generate graphs satisfying some rough constraints (you can make nauty generate only (bi)connected graphs, regular graphs, triangle/quadrangle free graphs,..) Use an external program to extract only the graphs you need with respect to ...


5

Somewhat like sorting algorithms in this regard, there is no "one size fits all" PRNG. Different ones are used for different purposes and there is a wide variety of design criteria and uses. It is possible to misapply PRNGs, such as using one for cryptography that it is not designed for. Wikipedia's entry on Mersenne Twister also mentions that it was not ...


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