Questions relating to (pseudo)randomness, random oracles, and stochastic processes.

learn more… | top users | synonyms

151
votes
25answers
12k views

Can a coin with an unknown bias be treated as fair?

This morning, I wanted to flip a coin to make a decision but no coins were in reach. There was however an SD card on my desk: Given that I don't know the bias of this SD card, would flipping it be ...
59
votes
3answers
1k views

Mathematicians shocked(?) to find pattern in prime numbers

There is an interesting recent article "Mathematicians shocked to find pattern in "random" prime numbers" in New Scientist. (Don't you love math titles in the popular press? Compare to the source ...
36
votes
3answers
5k views

Why does this not seem to be random?

I was running a procedure to be like one of those games were people try to guess a number between 1 and 100 where there are 100 people guessing.I then averaged how many different guesses there are. ...
35
votes
3answers
6k views

Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

I have a very simple simulation program, the sequence is: Create an array of 400k elements Use a PRNG to pick an index, and mark the element (repeat 400k times) Count number of marked elements. An ...
34
votes
5answers
5k views

How to find a random axis or unit vector in 3D?

I would like to generate a random axis or unit vector in 3D. In 2D it would be easy, I could just pick an angle between 0 and 2*Pi and use the unit vector pointing in that direction. But in 3D I ...
25
votes
5answers
6k views

Method of generating random numbers that sum to 100 - is this truly random?

I am writing a computer program that involves generating 4 random numbers, a, b, c, and d, the sum of which should equal 100. Here is the method I first came up with to achieve that goal, in ...
25
votes
9answers
14k views

What's the difference between stochastic and random?

What's the difference between stochastic and random? I've read in the Portuguese Wikipedia that there's a difference, but I still didn't see this point on English Wikipedia.
23
votes
4answers
13k views

Picking random points in the volume of sphere with uniform probability

I have a sphere of radius $R_{s}$, and I would like to pick random points in its volume with uniform probability. How can I do so while preventing any sort of clustering around poles or the center of ...
23
votes
5answers
3k views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
20
votes
7answers
6k views

Generate a random direction within a cone

I have a normalized $3D$ vector giving a direction and an angle that forms a cone around it, something like this: I'd like to generate a random, uniformly distributed normalized vector for a ...
19
votes
8answers
3k views

3 random numbers to describe point on a sphere [duplicate]

I'm currently working on a problem involving computer graphics and got into a discussion about whatever or not constructing a 3d vector out of 3 random points uniformly distributed points between -1 ...
16
votes
3answers
3k views

Choose a random number between 0 and 1 and record its value. Keep doing it until the sum of the numbers exceeds 1. How many tries do we have to do?

Choose a random number between 0 and 1 and record its value. Do this again and add the second number to the first number. Keep doing this until the sum of the numbers exceeds 1. What's the expected ...
16
votes
4answers
556 views

Powers of random matrices

Let $M$ be an $n \times n$ matrix whose elements are random reals in [0,1]. Two questions. What is the growth rate of the magnitude of the elements of $M^k$ as a function of $k$? It is definitely ...
16
votes
1answer
393 views

Flaw or not flaw in Excel's RNG?

I have a question about my understanding of an article of B.D. McCullough (2008) about Excel's implementation of the Wichmann-Hill random number generator (1982). First, a bit of context The ...
15
votes
2answers
484 views

Does $\pi$ satisfy the law of the iterated logarithm?

It is widely conjectured that $\pi$ is normal in base $2$. But what about the law of the iterated logarithm? Namely, if $x_n$ is the $n$th binary digit of $\pi$, does it seem likely (from ...
13
votes
4answers
632 views

How to efficiently generate five numbers that add to one?

I have access to a random number generator that generates numbers from 0 to 1. Using this, I want to find five random numbers that add up to 1. How can I do this using the smallest number of steps ...
13
votes
2answers
4k views

How can I pick a random point on the surface of a sphere with equal distribution?

I've got a random number generator that yields values between 0 and 1, and I'd like to use it to select a random point on the surface of a sphere where all points on the sphere are equally likely. ...
13
votes
3answers
4k views

uniform random point in triangle

Suppose you have an arbitrary triangle with vertices $A$, $B$, and $C$. This paper (section 4.2) says that you can generate a random point, $P$, uniformly from within triangle $ABC$ by the following ...
13
votes
1answer
5k views

Markov process vs. markov chain vs. random process vs. stochastic process vs. collection of random variables

I'm trying to understand each of the above terms, and I'm having a lot of trouble deciphering the difference between them (note, my mathematics training isn't very strong - so please go easy on the ...
13
votes
2answers
1k views

Apparent Paradox in the Idea of Random Numbers

This question is a bit less than rigorous, but it's only because I don't know how to formulate it rigorously. Suppose there was some machine, or function, or whatever that could output a random ...
13
votes
2answers
224 views

$e$ popping up in topic I'm unfamiliar with

I programmed up a little algorithm that goes like this: Fix two positive, real numbers, call them $\alpha$ and $\beta$. Generate a new, random, real number, $x \in [0,1]$ Set $\alpha$ = ...
12
votes
6answers
4k views

Choosing two random numbers in $(0,1)$ what is the probability that sum of them is more than $1$?

Choosing two random numbers in $(0,1)$ what is the probability that sum of them is more than $1$? Also what is probability of sum of them being less than $1$? I think the answer should be ...
12
votes
1answer
158 views

Fitting a parabola to separate two classes of points in the plane

Suppose we have a set of points $(x,y)$ in the plane where each point is either boy or a girl. Does there exists a randomized linear-time algorithm to determine if we can fit a parabola (given by a ...
11
votes
3answers
12k views

Sum of independent Binomial random variables with different probabilities?

suppose I have independent random variables $X_i$ which are distributed binomially via $$X_i \sim \mathrm{Bin}(n_i, p_i)$$. Are there relatively simple formulae or at least bounds for the ...
11
votes
3answers
731 views

Generation of unimodular matrices with bounded elements

Does anybody know what is the algorithm for generating random unimodular matrices (integer matrices with determinant $\pm 1$) whose elements do not exceed a given bound? Such an algorithm is mentioned ...
10
votes
7answers
643 views

Can true randomness come out of mathematical rules?

For example, prime numbers, they seem very random, and they are defined by a simple set of rules. I can't see how real randomness could exist in the real world, but what about mathematics?
10
votes
3answers
4k views

Is there a “most random” state in Rubik's cube?

Is there a state in Rubik's cube which can be considered to have the highest degree of randomness (maximum entropy?) asssuming that the solved Rubik's cube has the lowest?
10
votes
3answers
2k views

The pseudoness of pseudorandom number generators

Is there a reasonable statistic test one can do to standard random number generators (say, one of those that come built in in Python libs) which shows they are not really random? (By reasonable I ...
10
votes
5answers
761 views

Why do we need “perfectly” random numbers?

I periodically see articles about physicists or others coming up with a technique that generates a slightly more random number than was possible before, and how this is useful for encryption. But ...
10
votes
2answers
198 views

How can I randomly generate trees?

I want to randomly generate trees, i.e. undirected acyclic graphs with a single root, making sure that all possible trees with a fixed number of nodes n are equally likely.
9
votes
3answers
896 views

How can one create random numbers with special correlations?

Is it possible to create uniformly distributed real pseudo random numbers $x_1,x_2$, and $y_1,y_2,y_3\in$ $[0,1]$, subject to the following constraints: $$x_1^2+x_2^2=1$$ $$y_1^2+y_2^2+y_3^2=1$$ I ...
9
votes
2answers
10k views

Difference between logarithm of an expectation value and expectation value of a logarithm

Assuming I have a always positive random variable $X$, $X \in \mathbb{R}$, $X > 0$. Then I am now interested in the difference between the following two expectation values: $E \left[ \ln X ...
8
votes
4answers
2k views

Are irrational numbers completely random?

As far as I know the decimal numbers in any irrational appear randomly showing no pattern. Hence it may not be possible to predict the $n^{th}$ decimal point without any calculations. So I was ...
8
votes
3answers
2k views

What is golden ratio doing in this computer code?

In this file (related to random number generation), there is following line: private const int MSEED = 161803398; which resembles golden ratio. How come ...
8
votes
3answers
685 views

How do we check Randomness? [duplicate]

Let's imagine a guy who claims to possess a machine that can each time produce a completely random series of 0/1 digits (e.g. $1,0,0,1,1,0,1,1,1,...$). And each time after he generates one, you can ...
8
votes
3answers
202 views

Random Sequence of Alternating Increase/Decrease Numbers

The problem statement: Repeatedly pick a random number (uniformly-distributed) between $0$ and $1$. Keeping going while the second number is smaller than the first, the third number is larger than the ...
8
votes
3answers
192 views

Uniformly Random Tuples

Consider a multiset of natural numbers. As an example take $$ M = \{1, 2, 2, 3, 3, 3\} $$ If we treat copies of the same number as indistinguishable, there are 8 distinct 2-tuples we can form from ...
8
votes
1answer
375 views

Repeatedly Toss Balls into Bins

$n$ balls are randomly tossed into $m$ bins, each bin can hold $k$ balls. If a ball is tossed into a full bin (already has $k$ balls in it), it can be tossed repeatedly and randomly into the $m$ bins ...
7
votes
5answers
758 views

Is the product of uniformly distributed numbers, uniformly distributed too?

My question is simple, I think. If we took two random natural numbers $a$ and $b$ uniformly distributed in a specific range $[c,d]$, is $ab$ a uniformly distributed too? What if $a$ and $b$ are not ...
7
votes
2answers
981 views

How to generate REAL random numbers with some random and pseudo random

I'm doing (with Java) a very simple simulator (Queueing Systems..) that needs many random numbers (more than $10^5$). I know that Java Random class would give me all the random numbers I need, and ...
7
votes
2answers
1k views

Summing (0,1) uniform random variables up to 1 [duplicate]

Possible Duplicate: choose a random number between 0 and 1 and record its value. and keep doing it until the sum of the numbers exceeds 1. how many tries? So I'm reading a book about ...
7
votes
2answers
548 views

For any irrational number such as pi, would any sequence of length n appear in its decimal places?

If pi is an irrational number that goes on infinitely forever, does it mean that I can get any sequence of numbers of any length, and somewhere in the decimals of Pi, this sequence will exist. Eg. ...
7
votes
2answers
616 views

Accessible Intro to Random Matrix Theory (RMT)

I read this fascinating article: http://www.newscientist.com/article/mg20627550.200-enter-the-matrix-the-deep-law-that-shapes-our-reality.html Unfortunately all the other papers I find googling are ...
7
votes
1answer
15k views

'normally distributed random numbers' vs 'uniformly distributed random number'?

what is the difference between 'normally distributed random numbers' and 'uniformly distributed random number'? A answer in a layman language is appreciated :)
7
votes
1answer
139 views

Arithmetic background of this RNG code

I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
7
votes
2answers
836 views

Probability that a sequence repeats itself

Given an infinite sequence $a_n$ of uniformly random integers $0$ to $9$, what is the probability there exist an integer $m$ such that the sequence $a_1$ to $a_m$ is equal to that from $a_{m+1}$ to ...
7
votes
0answers
123 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
7
votes
0answers
786 views

Random 3D points uniformly distributed on an ellipse shaped window of a sphere

How can I generate random points uniformly distributed on the surface of a sphere such that a line that originates at the center of the sphere, and passes through one of the points, will intersect a ...
6
votes
3answers
741 views

Is it necessary that if a limit exists at a point it should be also defined at that point?

Say there exists a limit $\lim_{x \to x_0}f(x) = L$. Is it necessary that $f$ be defined at the point $x_0$ itself? Well, what I think of it is that it's OK to be undefined at that point because I ...
6
votes
2answers
391 views

number of reverses of direction to return in random walk

I am wondering if there are some studies about the number of reverses of direction to return to the starting point in random walk (either symmetric or non-symmetric), for example, its distribution and ...