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

learn more… | top users | synonyms

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 \...
4
votes
1answer
228 views

Invertible $N \times N$ matrix over ${\rm GF}(2)$ having on each row and column $N/2$ ones

As per the title, I'm looking for the name and for a way to construct a ${\rm GF}(2)$ square matrix of size $N$ with the following properties: All rows/columns should be linearly independent On each ...
14
votes
3answers
5k 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 ...
4
votes
3answers
3k views

Formula for Random

Since computers work off formulas, without greater knowledge one would assume that it would come up with the same answer for a set formula. However, you're able to tell it to generate a random number. ...
0
votes
1answer
1k views

Consequences of choice of a seed for random number generating algorithm?

Background I am trying to do a reproducible scientific analysis. My conclusions are not dependent on the random number generator, but the RNG does change the results ~1% between runs. I would like to ...
3
votes
2answers
2k views

Probability of Random number repeating

In the situation of having a high entropy random number generator, that generates numbers in the range of 0 and 2,147,000,000. If i have a list of 1,000,000 integer values, what are the chances that ...
1
vote
2answers
129 views

Are the values generated by non-linear equations truly random?

I was recently studying some literature on chaos theory and non-linear equations . where in various ciphers were created using non- linear equations like Lorenz equation . Are the data generated from ...
2
votes
1answer
422 views

Determining the period of a music player's “shuffle” feature

I ask this in a partly recreational, and partly research-related spirit, and I realize my problem might be ill-posed, so any suggestions for clarification might go a long way. Succinctly, my problem ...
3
votes
3answers
406 views

Deterministic random numbers generator using $p^n \mod q$

I figured that I can create a deterministic "random" numbers generator by utilizing a bit of "magic" that I picked up from some cryptography. However I seem to have missed a detail. Basically the ...
2
votes
3answers
274 views

Expected time of tree search algorithm on random input

We have a perfect binary tree on 2^k-1 nodes. Every node in the tree is marked with probability 1/2, and a node is either marked or unmarked. We want to find a marked node and return it. Our algorithm ...
0
votes
1answer
351 views

Proof for Minkowski reduced basis

I've read a few articles explaining the way to use the Minkowski reduced basis in a lattice in order to measure the uniformity of the output of a random number generator. However, I can't prove a ...
4
votes
1answer
641 views

Generalized Feedback Shift Registers

I find confusing some examples I have seen. Maybe you can help me to determine what is going on with them. A Generalized Feedback Shift Register (GFSR) sequence defines a sequence $\{W_{i}\}$ ...
3
votes
1answer
216 views

Max of multistep Gaussian walk vs max of multiple single-step Gaussian walks

Is there a relation between the max of a Gaussian random walk of 10 steps vs the max of 10 Gaussian random walks? Specifics (in Mathematica notation): ...
3
votes
0answers
1k views

Bays-Durham Shuffling

Reading "Random number generation and Monte Carlo methods" by James E. Gentle, I encountered an example concerning the Bays-Durham Shuffling algorithm whose result I can't reproduce. Basically, such ...
16
votes
4answers
569 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 ...
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 ...
5
votes
2answers
404 views

Polygonal billiards and uniform distribution

According to this article in Wikipedia: A billiard is a dynamical system in which a particle alternates between motion in a straight line and specular reflections from a boundary. When the particle ...
1
vote
1answer
336 views

Random assignment in blind experiments and “fair / just coin”

In blind experiments subjects are randomly assigned to one of groups. The most commonly used solution is to use (equivalent of) a coin toss, with the same probability to be assigned to each group. I ...
7
votes
2answers
658 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 ...
10
votes
2answers
199 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.