# Tag Info

## Hot answers tagged randomized-algorithms

49

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.

25

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $... 18 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 ... 17 if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement The application of this algorithm is trivial - you use it whenever you want to compute a median of a set of data (array in other words). This data may come from different domains: astronomical observations, social science, ... 17 You seem to have misunderstood what the key is. In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that. For your proposed ... 13 Median filtering is common in reduction of certain types of noise in image processing. Especially salt and pepper noise. It works by picking out the median value in each color channel in each local neighbourhood of the image and replacing it with it. How large these neighbourhoods are can vary. Popular filter sizes (neighbourhoods) are for example 3x3 and ... 12 Your argument appears to be perfectly valid (Fisher-Yates does indeed require$\log (n!)$bits of randomness), the discrepancy comes in by making different assumptions about the complexity of the random number generation. You're assuming generating a random number between$0$and$n$takes$O(\log n)$. But, when saying that the Fisher-Yates shuffle is$O(n)...

12

The formal, unambiguous way to state this is “terminates with probability 1” or “terminates almost surely”. In probability theory, “almost” means “with probability 1”. For a probabilistic Turing machine, termination is defined as “terminates always” (i.e. whatever the random sequence is), not as “terminates with probability 1”. This definition makes ...

12

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to ...

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/... 11 Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental concept of a one time pad and the notion of mathematically provable perfect secrecy is that the pad material is truly random. And it must never ever be reused, even ... 11 Your process is a textbook example of a branching process. Starting with one$E$, we have an expected$3/2$many$F$s,$9/4$many$T$s, and so$9/8$many remaining$E$s in expectation. Since$9/8 > 1$, it is not surprising that your process often failed to terminate. To gain more information, we need to know the exact distribution of the number of$E$-... 10 Computing medians is particularly important in randomized algorithms. Quite often, we have an approximation algorithm that, with probability at least$\tfrac34$, gives an answer within a factor of$1\pm\epsilon$of the true answer$A$. Of course, in reality, we want to get an almost-correct answer with much higher probability than$\tfrac34$. So we ... 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 ... 9 Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days it aimed to capture the notion of "practical computation" (even particular flavors such as parallel computation, supposedly captured by NC), it has since ... 9 Suppose that the array has length$n$. Since you are making$n$random choices of numbers from 1 to$n$, the probability to obtain any specific permutation is of the form$A/n^n$, for some integer$A$. Therefore your algorithm could work only if$n^n/n!$is an integer, which is only the case when$n \leq 2$. More concretely, if you shuffle the array$1,2,3$,... 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 ... 8 Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem Graph Non-Isomorphism (GNI): Input: Two graphs$G_0$and$G_1$with$n$vertices each. Output: Accept if and only if$G_0$and$G_1$are not ... 8 The two terms randomized algorithms and probabilistic algorithms are used in two different contexts. Randomized algorithms are algorithms that use randomness, in contradistinction with deterministic algorithms that do not. Probabilistic algorithms, for example probabilistic algorithms for primality testing, are algorithms that use randomness and could make ... 8 You made a crucial change to the question. I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well. To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot. Here are some ... 8 Yes, the constant is entirely arbitrary. Call an algorithm a$p$-algorithm if: When the correct answer is NO, it always answers NO. When the correct answer is YES, it answers YES with probability at least$p$. Note that the probability in the YES case is only over the algorithm's coin tosses. Given a$p$-algorithm and a constant parameter$m$, we ... 8 There are implementations of Quicksort (the partitioning algorithm, specifically) which deal badly with duplicates. No matter how much you randomize -- shuffling the input, random choice of the pivot, random choice of the pivot with sampling, ... -- if all entries are the same (or there are only constantly many distinct values), these bad implementations ... 8 (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 ... 8 tl;dr: You can make a rough probabilistic judgement in$O(1)$time Let's assume you are willing to settle on a test which differentiates "good" matrices$A,B$from "pretty bad"$A,B$, in the following sense: If$A \times B = I$, the test will accept with high probability. If$A \times B$is far* from$I$, the test will reject with high ... 7 The approach to quantum computing that you are referring to is something called the adiabatic model. It's actually based on continuous time evolution of quantum systems, rather than on discretized-time models (i.e. no gates). It turns out that it is possible to approximate continuous time evolution with a discrete set of gates, and so the algorithm can be ... 7 Let's suppose that we have a polynomial time randomized algorithm$A$for a decision problem$\Pi$with the property that $$\mathrm{Pr}[A \text{ is right}] > 1/2$$ for all inputs. (In particular, independent of the input length$n$.) We can use Chernoff bounds to show something stronger, namely that for any fixed$c$, there is a polynomial time, ... 7 We can! However, the PCP theorem does not say that we can solve the problem using$\log n$bits of randomness. It says that we can verify a solution with$\log n$bits. Recall that a standard definition of NP is the class of languages for which there is a deterministic, polynomial-time verifier: For each$x$in the language, there is a certificate$y$so ... 7 There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time$\Theta(n\log n)\$. ...

7

The question "Does it terminate?" isn't well-formed. You need to define more precisely what you mean by that question before it can be answered. Is it guaranteed to terminate on all possible execution traces? No. There exists an execution trace where it never terminates. Does it terminate with probability one? Yes. If you flip a coin until you first ...

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