49
votes
Can we generate random numbers using irrational numbers like π and e?
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 ...
- 81.1k
28
votes
Can we generate random numbers using irrational numbers like π and e?
It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.
- 27.4k
25
votes
How can I quickly judge whether matrix A is the inverse matrix of B?
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 ...
- 626
18
votes
Accepted
Can we generate random numbers using irrational numbers like π and e?
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 ...
- 522
17
votes
Accepted
Are there any algorithms or data structures that need to find the median value of a set?
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 ...
- 9,707
17
votes
Accepted
Problem with the pseudo random number generator One-Time-Pad
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 ...
- 81.1k
13
votes
Are there any algorithms or data structures that need to find the median value of a set?
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 ...
- 231
12
votes
Accepted
Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
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$...
D.W.♦
- 152k
11
votes
Problem with the pseudo random number generator One-Time-Pad
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 ...
- 1,602
11
votes
Accepted
Generating random words by grammar
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 > ...
- 274k
10
votes
Accepted
Why is ZPP = RP ∩ co-RP?
The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.
Markov's inequality ...
- 4,787
10
votes
Are there any algorithms or data structures that need to find the median value of a set?
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\...
- 81.1k
9
votes
Accepted
Choosing a random bit from a bitmap
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,...
- 274k
9
votes
Accepted
Why is randomness a problem? (i.e. why do we care about derandomization?)
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 ...
- 274k
9
votes
Why shuffling by picking random position in all array instead of a part is not correct
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$....
- 274k
9
votes
Accepted
Random restarts for unsatisfiable instances
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 ...
- 8,013
8
votes
Accepted
Why is the probability used in the definition of RP complexity classes, arbitrary?
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 ...
- 274k
8
votes
Are there adversarial inputs for randomized quicksort?
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, ...
- 71.8k
8
votes
How can I quickly judge whether matrix A is the inverse matrix of B?
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,...
- 955
7
votes
Is there a random shuffle algorithm using only true /false?
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 ...
- 274k
7
votes
Isn't polynomial identity testing over arithmetic *expressions* trivial?
For a univariate polynomial $p(x)$, yes, it's that easy.
For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works.
In particular, when you write "a polynomial of degree $d$ ...
D.W.♦
- 152k
7
votes
What does the "principle of deferred decisions" formally mean
The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.
One way is that you can toss a coin yourself at the exact step when you ...
- 1,188
7
votes
Accepted
How can Karger's algorithm (and other randomized algorithms) be used in practice?
Karger's algorithm is a randomized algorithm. It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach.
If we do one ...
D.W.♦
- 152k
7
votes
Accepted
Randomized algorithm for 3SAT
The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.
Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm ...
- 274k
7
votes
Problem with the pseudo random number generator One-Time-Pad
A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish ...
- 13.3k
7
votes
Can we generate random numbers using irrational numbers like π and e?
(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 ...
- 1,035
7
votes
Accepted
Expected length of a random walk on a line
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. ...
- 274k
7
votes
Generating random words by grammar
As Yuval has noted, this way of randomly generating recursive data structures is known to (usually) end up with an infinite expected size.
There is, however, a solution to the problem, that allows ...
- 370
7
votes
Accepted
Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
It appears your question is equivalent to sampling uniformly at random from the integer partitions of $N$, but constrained so that your partition has $\le B$ parts.
If that is correct, there are ...
D.W.♦
- 152k
6
votes
Accepted
Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?
Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors ...
- 274k
Only top scored, non community-wiki answers of a minimum length are eligible