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 ...
David Richerby's user avatar
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.
gnasher729's user avatar
  • 29.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 ...
phan801's user avatar
  • 616
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 ...
Dmitry Grigoryev's user avatar
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 ...
fade2black's user avatar
  • 9,817
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 ...
David Richerby's user avatar
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 ...
mathreadler's user avatar
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.'s user avatar
  • 158k
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 ...
Paul Uszak's user avatar
  • 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 > ...
Yuval Filmus's user avatar
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 ...
Sarvottamananda's user avatar
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\...
David Richerby's user avatar
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 ...
Kyle Jones's user avatar
  • 8,071
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 ...
Yuval Filmus's user avatar
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$....
Yuval Filmus's user avatar
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, ...
Raphael's user avatar
  • 72.3k
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,...
einpoklum's user avatar
  • 965
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 ...
Yuval Filmus's user avatar
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 ...
Banach Tarski's user avatar
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.'s user avatar
  • 158k
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.'s user avatar
  • 158k
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 ...
Yuval Filmus's user avatar
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 ...
Ariel's user avatar
  • 13.4k
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 ...
Ayrat's user avatar
  • 1,055
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. ...
Yuval Filmus's user avatar
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 ...
phipsgabler's user avatar
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.'s user avatar
  • 158k
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 ...
mhum's user avatar
  • 2,032
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....
Yuval Filmus's user avatar

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