# Tag Info

## Hot answers tagged randomized-algorithms

47

For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator. Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating but it's a terrible generator of random digits, since the answer is "always" zero, occasionally one, and never anything else. We don't actually know if every ...

29

It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.

17

The most obvious disadvantage is the unnecessary complexity of PRNG algorithms based on irrational numbers. They require much more computations per generated digit than, say, an LCG; and this complexity typically grows as you go further in the sequence. Calculating 256 bits of π at the two-quadrillionth bit took 23 days on 1000 computers (back in 2010) - a ...

9

There is some research in this area. In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both satisfiable and unsatisfiable SAT instances. The theoretical justification for the speedup is that in CDCL solvers a restart allows the search to benefit from ...

7

(updated after many people pointed out that random number generator is not the same thing as a single normal sequence) If you ask whether you can get a normal sequence out of $\pi$ (i.e., all numbers appear uniformly), then there are several answers on mathoverflow. For example, the answer about Distribution of the digits of Pi says: ...it is believed ...

7

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. When $p = 1/2$, the situation is more complicated. Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move ...

4

Yes. Your algorithm can return all permutations. You can prove it by fixing any arbitrary permutation $\pi$ of the input string str and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of str can match the last $i$ characters of $\pi$. For $i=0$ this is trivial. For $i>0$: Let $n$ be the lenght of str, $... 4 One possible solution to make this as simple as possible to quickly get a working algorithm would be as follows. The simplest layout is of course 12C (12 curved tracks all with the same orientation (relative to each other), and forming a simple circle. This will be the basis upon which we can build on. So the basic algorithm will be to maintain the 360 ... 4 Firstly, a frame challenge: A computer can create a valid layout using all of the tracks and if the algorithm is good, perhaps in a few seconds You don't need the algorithm to run in a few seconds. You need output in a few seconds. I don't see that there's anything stopping you from setting a brute force layout cruncher running on a computer in the ... 4 Asympotically, you'll need$\Theta(n^2 \log n)$comparisons. Suppose$x_{(1)},\dots,x_{(n)}$denotes the elements in sorted order. Then if you don't see a comparison between$x_{(1)}$and$x_{(2)}$, you will have no way to tell which order they should appear in. The same is true of every pair of adjacent element. So, there are$n-1$coupons (one per ... 3 Let's start with your second question. A random running time is a running time which is a random variables. As a simple example, consider an algorithm which tosses a fair coin until it come up heads. The running time is a random variable whose distribution is, roughly speaking, geometric. This is not so different from the randomized median algorithm: every ... 3 Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states: We can uniformly generate a matrix and its inverse in time$2M(n) + \mathbb{E}[O(n^2)]$. Where$M(n)$is the time it takes to multiply two$n \times n$matrices. Unfortunately this is not better than what you had hoped for. 3 You already proved in First part that using random assignments to the values it solves$\frac{m}{2}$equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability$\frac{1}{2}$on every random assignment. So we can use the following algorithm to solve this problem: E = Unsolved equations (... 3 Given an instance of knapsack, multiply all values by$k+1$. Any solution satisfyign$OPT(I) - P_A(I) \leq k$is in fact optimal, so you could use such an algorithm to solve knapsack. 3 Let$P$be the distribution of$i^*, which you can calculate explicitly: \begin{align*} p_i := \Pr[P=i] &= \left(1-\frac{i-1}{n}\right)^k - \left(1-\frac{i}{n}\right)^k. \end{align*} This is the probability that all samples are at leasti$minus the probability that they are all at least$i+1$. The counter$C(i)$has binomial distribution$\...

3

I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not ...

3

Here is the simplest algorithm, which is efficient when $k$ is much smaller than $n$ relatively. Input: two positive integers $n$ and $k$ with $k\le n$ Output: a random permutation of $k$ integers from $1,2,\cdots,n$ Algorithm: Let arr be an array of size $n$ and a default value that is not True. Let out be an empty array. Let i be a random integer in $[0,... 3 This is just speculation, but perhaps what VLC is attempting is to simulate... perfect randomness. That is, each song is picked uniformly at random, independently of previous songs. According to the coupon collector problem, if you have$n$songs in your list and want to hear all of them, you will have to wait for roughly$n\ln n$songs to be played. By that ... 2 Reservoir sampling solves exactly this problem in$O(n)$time. When$n$is really large, but you can calculate the$i$th element just from the index$i$in$O(1)$time then you can simulate the sampling by getting the first$k$elements from a random permutation of$\{1, \dots, n\}$in$O(k \log n)$time using Sometimes-Recurse Shuffle. 2 Answer to Question 1 We can assume without loss of generality that the original ordering is the usual one:$a_1 < a_2 < \cdots < a_n$. Some ordering$\pi$is compatible with our observations if whenever$\pi(i) < \pi(j)$for some$i > j$, this observation is missing. In other words,$\pi$is compatible with probability$(1-p)^{\operatorname{...

2

If you have to create the maze: Without boundaries Generated uniformly Generated from a seed It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze. Daedalus has lots of features and implements all the algorithms on this page. To generate a really big maze in Daedalus, start the ...

2

The class BPP (and related classes such as RP, coRP, and ZPP) deal with decision problems. This means the algorithms corresponding to these classes may only produce "yes" or "no" answers. This notion does not quite match your algorithm, which is actually solving a search problem (i.e., the solution set is a subset of some arbitrary set of outputs). At any ...

2

Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts? I first looked at The Art of Computer Programming Volume 4A ("Combinatorial Algorithms Part 1"), specifically Section 7.2.1.3 "Generating all combinations" (which comes under Section 7.2.1 "Generating Basic Combinatorial Patterns", itself under 7.2 "...

2

You explain how to convert a ZPP machine to a BPP machine. This means that if a problem is in ZPP, then it is also in BPP. In other words, ZPP is contained in BPP.

2

For a permutation $\pi$, let $\pi(i\;j)$ be the permutation obtained by switching the places of elements $i$ and $j$. Since $\pi(i\;j)(i\;j) = \pi$, we can partition the set of all permutations over the elements of $A$, into $n!/2$ pairs $\{\pi,\pi(i\;j)\}$. Consider what happens to $A$ after permuting by $\pi$ and by $\pi(i\;j)$. In exactly one of these ...

1

It provides a good random number right until you realize how it was produced, as with many pseudo random number. The irrational (non algebraic and non transcendental) numbers you have chosen are common and so easier guessed then others. I can see no issue with this method provided you choose less commonly seen generators.

1

In general, this approach does not work: "randomness" does not mean that you get a lot of different digits, but there are other aspects as well. For example, a classic test is to see if all two-digit, or three-digit etc. combinations occur with the same frequency. This would be a very simple test, which can rule out obvious non-random results, but is still ...

1

Some graphs have less than the maximum. This shouldn't be a surprise.

1

"Maximum" here means that no graph can have more than $n \choose 2$ minimum cuts. Obviously, you can come up with graphs (or infinite families of graphs) that have fewer minimum cuts, like say $n-1$. This is less than $n \choose 2$ which is perfectly fine, so this is no contradiction. In other words, the result only means that you can't come up with graphs ...

1

If $c < 1/2$ then for any problem there is an algorithm that answers correctly with probability at least $c+1/n$, say. For small $n$, the algorithm just outputs the hardwired correct answer. When $n$ is large enough so that $c + 1/n \leq 1/2$, the algorithm just tosses a coin. What went wrong? For BPP amplification to work, we need a gap between the ...

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