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

learn more… | top users | synonyms

6
votes
0answers
318 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 ...
5
votes
0answers
232 views

expectation value for minimum distance between random variables

note: edited to clarify boundary issue Suppose $x_i$, $i=1\dots n$, are randomly drawn from a uniform circular distribution between 0 and 1 (using periodic boundaries). Let $d_i$ be the distance ...
4
votes
0answers
88 views

Entries of a Haar distributed unitary matrix

The eigenvector matrix of a Wishart matrix is Haar distributed and that implies that the eigenvectors are uniformly distributed on a sphere. I'm interested to know what is the distribution of ...
4
votes
0answers
56 views

Pairwise spacings of an ordered sequence of uniform random numbers

Given an ordered list of $m$ uniform random numbers in the range $1$ to $n$ $$a_{1} \le a_{2} \le \ldots \le a_{m}, \forall a_{i}: a_{i}\in [1;n] \cap \mathbb{N}$$ compute the pairwise spacings of ...
4
votes
0answers
105 views

Completeness of random walks in multiple dimensions?

I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than ...
4
votes
0answers
813 views

Random graph connectivity, and the existence of isolated vertices

Here $G_{n,p}$ represents the Erdős-Rényi random graph model, where the graph has order $n$ and each edge is added independently with probability $p$. I am faced with proving the following claim: ...
3
votes
0answers
22 views

Magnitudes of roots of random polynomials

I'm looking at the roots of random polynomials with integer coefficients, and constant term=leading term = 1. Using the Mathematica code ...
3
votes
0answers
45 views

Random Sampling of vectors on the Complex Unit Sphere

This is my first post in these forums. Working in Mathematica, I would like to generate a large number (10000) of randomly sampled vectors on the complex unit sphere in n dimensions. I am not ...
3
votes
0answers
35 views

What is the most important test for a uniform random number generator?

What is the most important test for a uniform random number generator ? Is there a single most important test or a set? I am a using some analytically arrived at answers to probability problems and ...
3
votes
0answers
39 views

Can I solve this probabilistic problem or do I need more data?

This problem happened to me almost 3 years ago and I just discovered this site by luck, so I want some help to know if this problem is solvable (if so, I would like to know how to solve it as well as ...
3
votes
0answers
58 views

Fractals vs. “neatness” / order

I've seen a lot of high level videos on fractals, etc, and how they might apply to the real world. So a tree is branches with branches with branches, and our blood vessels branch and then branch ...
3
votes
0answers
182 views

Simulation and Stochastic Processes

Supposing we want to take a sample from the distribution $p(x)=cp^*(x)$ where $c$ is the normalization constant and $p^*(x)$ is given by $$p^*(x)=0.5\exp(-(x-\mu_1)^2)+0.5\exp(-(x-\mu_2)^2).$$ ...
3
votes
0answers
552 views

Notation for sampling random variate

Is there standard notation for sampling a value from a probability distribution? Like, if I had a random variable $X$, setting $x$ to whatever value I happened to sample from $X$ on this occasion? I ...
3
votes
0answers
905 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 ...
2
votes
0answers
13 views

spectral norm of a sparse Gaussian matrix

Suppose $G$ is an $m \times n$ matrix such that each entry of $G$ is a standard normal variable. We know that the spectral norm of $G$ scales as $\sqrt(m) + \sqrt(n)$. Now, given a set of indices $S$ ...
2
votes
0answers
33 views

How do you calculate randomness?

Suppose I receive a list of 1 million coinflips, and I want to know how likely it is that the list was randomly generated. My first thought would be to count the number of heads and tails, which ...
2
votes
0answers
23 views

What is the test of for randomness

How do you tell if a large sequential sample taken from a 0-1 rectangular parent - and presented as random - is truly random?
2
votes
0answers
59 views

Randomness in a sequence

For a function $f$ consider a random sequence $a_{n+1}$ can be either $a_n+f(a_n)$ or $a_n-f(a_n)$ Given that the next term in the sequence is subtracting $f(a_n)$ from the previous term 50% of the ...
2
votes
0answers
64 views

“Alice and Bob” problem with matrices

Alice has a binary matrix $A$, and Bob has a binary matrix $B$. Both matrices are of size $n \times n$. Alice and Bob want to check if the matrices are equal except for exactly $1$ entry. Alice has to ...
2
votes
0answers
55 views

Knuth shuffle : Is there a reciprocal to the factorial?

I have looked into the Knuth collection shuffle algorithm with pseudorandom number generators. They say that a PRNG with a seed state of $19937$ bits (like one of the Mersenne Twisters) can shuffle a ...
2
votes
0answers
66 views

Random walk with $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} < \infty$

Consider a random walk started at $S_0=0$, denoted $S_n = \sum_{k=1}^{n}X_k$, where $X_1$, $X_2$... are the i.i.d increments. If we have $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} ...
2
votes
0answers
94 views

Random pair generation?

Suppose there are 6000 people, there will be a combination of $$\binom{6000}{2}$$ ways for 2 people to be chosen out. Now the task is to randomly choose 5000 pairs of people in the total 6000 ...
2
votes
0answers
117 views

Using an elliptic curve to create pseudo random number

I recently started learning about encryption. I read about how elliptic curves can be used to create pseudo random numbers (and how the nsa might have abused this fact to create a backdoor in ...
2
votes
0answers
42 views

explicit random cake cutting

I like to split a given interval, let's say $[0,1]$, randomly to a given number $n$ parts. A random input may be provided, like for example a sequence of random numbers $\omega=(r1, r2, ...
2
votes
0answers
88 views

How to construct a uniform joint distribution

I have a question that is critical to my work, but I am not sure if it is any possible. Assume that you have two uniform random variables X and Y. The product distribution of Z=XY is not a uniform. ...
2
votes
0answers
79 views

Packing a larger sphere with smaller spheres in high dimensions

We were discussing today the probability of leaving a point uncovered while trying to fill a larger sphere by randomly throwing in smaller spheres. Here's the argument: We are working in ...
2
votes
0answers
146 views

Finding functions where the increase over a random interval is Poisson distributed

I'm trying to construct a type of function $f(t_1, t_2)$ that counts the number of deterministically simulated Poisson events between two points in time. We can use a single valued function ...
2
votes
0answers
126 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
0answers
77 views

What's the definition of a random number?

What sequence of numbers can I call as random number? What's the right way of getting $n$ random numbers? Are the numbers generated by "dice", too known as random numbers? Can a machine (computer), ...
2
votes
0answers
371 views

Probability distribution of the product of two independent complex gaussian random variables

I have to calculate the pdf of $Z = X*Y$, where $X \in \mathcal{C}(\mu_x,\Sigma_x)$ and $Y \in \mathcal{C}(\mu_y,\Sigma_y)$, where $\mathcal{C}$ is a complex distribution. It can be assumed that ...
2
votes
0answers
96 views

Approximability of continuous sampling by discrete sampling - definitions?

Are there standard definitions that express the notion that sampling from a given continuous random variable can be approximated "to any desired degree of accuracy" by sampling from an appropriately ...
2
votes
0answers
535 views

Prove that $aX + bY$ is a random variable for all $a, b$ in $\mathbb{R}$

Given $X$ and $Y$ as random variable, how to prove that $aX + bY$ as random variable for all $a, b$ in $\mathbb{R}$? (from Karr) $$ \{X + Y <t\} = \bigcup\limits_{r\in\mathbb Q}\{X < ...
2
votes
0answers
53 views

Generating random vectors in a n-ring

I've seen many different approaches to generate a random vector in the ($n-1$)-sphere and in the $n$-ball. One of them is generating a normal n-vector v (all components $x_i\sim N(0,1)$) and then ...
2
votes
0answers
267 views

Are these numbers “random”?

The figure below shows 2000 points in (x,y) coordinates that are supposed to be high quality pseudorandom numbers. However, when I zoom in on any area lots of points are lined up along line ...
2
votes
0answers
76 views

Probability of ball ownership

$N+M$ people play a game of balls. Initially, N people hold N green balls (each person holds a ball), and M people hold no balls. Assume $M<N$. Then, M red balls are divided randomly - each ball ...
2
votes
0answers
48 views

Generate random numbers that are sums of hidden variables

I have $Y = A X$ where: $Y$ is an $m$ vector of random variables $X$ is an $n$ vector of random variables, uniformly distributed in $[0, 1]$ $m \ll n$, ($n$ ~ $m!$) $A$ is an $m \times n$ $0/1$ ...
2
votes
0answers
108 views

Modeling Sample Covariance Matrix based on concepts from Random Matrix Theory

I am working on a signal processing problem where I want to model the measurement sample covariance matrix (SCM) as random matrix and hence use the results from Random Matrix Theory (RMT). Let ...
2
votes
0answers
97 views

Likelihood Function of Random Process

Given the following data: $$ x(t) = A + \omega(t) $$ where $ \omega(t) $ is an AWGN with zero mean, what would be likelihood function $p(x(t);A)$? I know it could be proven to be: $$ p(x;A) = C ...
2
votes
0answers
127 views

LFSR with limited numbers of runs?

Is there a way to construct a linear feedback shift register (LFSR) which outputs no more than k consecutive 1s or 0s? (It would have to be not a maximal-length ...
1
vote
0answers
7 views

correlation between minimum singular values of submatrices

I have one question regarding how to measure the correlation between minimum singular values of submatrices extracted from a large random matrix. Given a m*n random matrix $\mathbf{A}$, the ...
1
vote
0answers
17 views

When is a coupling ''natural''?

The definition of coupling is written below. In some articles, I found the term "natural coupling". When is a coupling said to be ''natural''? Definition of coupling between two random variables: Let ...
1
vote
0answers
57 views

Conceptual Understanding of a Simple Random Process

I have a simple discrete time random process that with probability $0.5$ chooses a deterministic sequence so that $X(t) = -1$, for $t<1$ and $X(t) = +1$ for $t \geq 1$, similarly with probability ...
1
vote
0answers
26 views

Lyapunov exponents of dual / adjoint / transpose random dynamical system (RDS)

Consider the the state of a system at time $n$, $X_n$, as the action of a product of i.i.d. $d\times d$ random matrices acting on a $d$ dimensional vector $X_0$, so we have $$X_n = A_n \cdots ...
1
vote
0answers
16 views

Fourier transform of a real white noise on a 3D cubic lattice

I'm facing the following problem: I have a cubic domain of side $L=2\pi$; this domain is divided in a cubic grid, each side is divided in $N$ points, where $N$ is an even integer number. the ...
1
vote
0answers
28 views

How to perform sampling using O(log n) random bits per sample irrespective of the values of pi?

I am not able to find a sampling for the following problem. "Consider a problem of using a source of unbiased random bits to generate samples from the set S = {0,1,...,n-1} such that the element 'i' ...
1
vote
0answers
55 views

How can non-binary data be tested for distinguishability from random?

Given a large string of Base-N digits (in other words, not necessarily binary), is there software or an algorithm that can output whether the data is reasonably pseudorandom or reveals a pattern? In ...
1
vote
0answers
26 views

Is there a such thing as a quasi-random shuffle?

I've recently experimented with Quasi-random numbers in monte-carlo applications. Is there a way to construct a quasi-random shuffle? By that I mean can I take a sequence $Q$ and shuffle it to produce ...
1
vote
0answers
13 views

Even dirstibution of a small set of random choices into a small set of buckets

Is there a way to evenly distribute randomly selected small set of items from a relatively larger set into to a small number of buckets using a hash function? For ex: Randomly select 20 numbers from ...
1
vote
0answers
26 views

What is the deciability of randomness?

Let f(n) be a function that returns 1 iff n consecutive ...
1
vote
0answers
62 views

Generating a random combination in O(k)?

I need to generate a "fair" random combination of $k$ items chosen from $n$ choices. All the algorithms I've been able to find so far (reservoir sampling, Fisher-Yates shuffle, ...) are of $O(n)$ ...