50
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 ...
- 82.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.
- 31.4k
24
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 ...
- 614
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 ...
- 532
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,877
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 ...
- 82.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.♦
- 164k
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,612
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 > ...
- 278k
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\...
- 82.1k
10
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,119
10
votes
Accepted
Proof for boosting success probability of a random algorithm with binary output
The proof I know of uses a weak version of Chernoff bound:
If $X_1, X_2, …, X_n$ are independent Bernoulli random variables of same parameter $p$, and $X = \sum\limits_{i=1}^nX_i$, then:
$$\mathbb{P}(...
- 16k
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$....
- 278k
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 ...
- 278k
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,...
- 995
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.♦
- 164k
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 ...
- 278k
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.5k
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,085
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. ...
- 278k
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.♦
- 164k
6
votes
Accepted
Uniformly Random Nested Subset Pairs
For the sake of simplicity, I will assume that: 1) empty sets are allowed, 2) we count a set as a subset of itself (i.e.: both the big set and small set can represent the same set). If these ...
- 2,146
6
votes
Accepted
What is the difference between Simulated Annealing and Monte-Carlo Simulations?
Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness....
- 278k
6
votes
Accepted
Returning random integer from interval based on last result and a seed
I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and ...
D.W.♦
- 164k
6
votes
Accepted
Is there some kind of expected error margin for my Monte Carlo algorithm?
Suppose that you are trying to estimate some quantity $\mu$ by performing some random experiment $X$ with mean $\mu$ and variance $\sigma^2$. In order to obtain a better estimate, you can repeat the ...
- 278k
5
votes
Accepted
Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?
You pretty much have the answer in front of you.
For any vertex $v$, the cut $\left(\left\{v\right\},V\setminus\left\{v\right\}\right)$ has $\text{deg}(v)$ crossing edges.
If there exists a vertex ...
- 13.5k
5
votes
Are there any algorithms or data structures that need to find the median value of a set?
The median of medians has some applications:
Finding a pivot for quicksort, which brings its worst-time complexity to $ O(n \log n)$.
Finding a pivot for quickselect, bringing it's worst-time ...
- 88
5
votes
Can an algorithm be truly non-deterministic?
There are two meanings of non-deterministic.
Meaning #1: nondeterministic means the algorithm uses non-determinism, in the sense of a non-deterministic Turing machine: in other words, at each step the ...
D.W.♦
- 164k
Only top scored, non community-wiki answers of a minimum length are eligible