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.


22

First, let us make two maybe obvious, but important assumptions: _.random_item can choose the last position. _.random_item chooses every position with probability $\frac{1}{n+1}$. In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here: For the singleton list there is only one possibility, so it is ...


19

If the input array is distributed uniformly at random then (as you noted) there is no difference between always picking an element at a fixed position (for example the middle one as you suggest) or picking an element chosen at random. If however your input array is not really in random order (which happens to be the case in almost all practical scenarios) ...


17

Polynomial identity testing admits a randomised polynomial time algorithm (see the Schwartz-Zippel lemma), and we currently don't have a deterministic polynomial time or even a sub-exponential time algorithm for it. Game tree evaluation Consider a complete binary tree with $n$ leaf nodes each storing a 0/1 value. The internal nodes contain OR/AND gates in ...


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 ...


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 ...


15

The question really depends on what is the precise definition of a 2-hop. If by a 2-hop you mean the set $$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$$ then the current answer is no, you cannot do it faster than $O(n^{\omega})$ where $\omega$ is the usual constant associated with the complexity of performing the matrix product. ...


13

First of all, I will assume that by Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$ you actually mean Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly ...


13

So basically, you want to know if there is any sorting algorithm which wouldn't degrade from its average case if given a compare function similar to: int Compare(object a, object b) { return Random.Next(-1,1); } ... where Random.Next() is some method that will produce a randomly-generated integer between a specified inclusive lower and upper bound. The ...


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

Suppose your array has $n$ elements. As you have noted, the median is always in the bigger part after the first partition. The bigger part has size at most $\alpha n$ if the smaller part has size at least $(1-\alpha) n$. This happens when you pick a pivot that isn't one of the smallest or largest $(1-\alpha) n$ elements. Because $\alpha > 1/2$, you ...


12

An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the ...


12

Vor's answer gives the standard definition. Let me try to explain the difference a bit more intuitively. Let $M$ be a bounded error probabilistic polynomial-time algorithm for a language $L$ that answers correctly with probability at least $p\geq\frac{1}{2}+\delta$. Let $x$ be the input and $n$ the size of the input. What distinguishes an arbitrary $\...


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 ...


11

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)...


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 ...


10

Any algorithm that compares the same two elements twice is not a very clever algorithm, and in particular such an algorithm would perform less well than the most common sorting algorithms (merge-sort, quicksort, bubble-sort, insertion-sort). Any algorithm that compares pairs of elements at most once has the same (average) runtime cost regardless of the ...


10

That looks correct to me. The difference between BPP and PP is that for BPP the probability has to be greater than $1/2$ by a constant, whereas for PP it could be $1/2+ 1/2^n$. So for BPP problems you can do probability amplification with a small number of repetitions, whereas for general PP problems you can't.


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 ...


10

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 ...


9

Your coin flips form a one-dimensional random walk $X_0,X_1,\ldots$ starting at $X_0 = 0$, with $X_{i+1} = X_i \pm 1$, each of the options with probability $1/2$. Now $H_i = |X_i|$ and so $H_i^2 = X_i^2$. It is easy to calculate $E[X_i^2] = i$ (this is just the variance), and so $E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ from convexity. We also know that $X_i$ ...


9

Due to the dubious nature of the question, I only provide hints. Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not? For a proof, you will have to proceed inductively. In the step, you ...


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

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

The probabilistic method is typically used to show that the probability of some random object having a certain property is non-zero, but doesn't exhibit any examples. It does guarantee that a "repeat-until-success" algorithm will eventually terminate, but does not give an upper bound on the runtime. So unless the probability of a property holding is ...


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 ...


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