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

learn more… | top users | synonyms

6
votes
0answers
356 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
245 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
103 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
60 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
110 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
839 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
26 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
53 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
40 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
40 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
584 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
934 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
25 views

A set of conditions to prove or disprove randomness

I am trying to understand the heuristic connection between fitting a normal distribution to a dataset and the definition of what constitutes a random process. If a normal distribution fits your ...
2
votes
0answers
15 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
35 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
66 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
60 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
69 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
100 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
132 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
92 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
82 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
136 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
58 views

Are there algorithms related to cloud shapes?

This is going to be applied in programming, but I thought the question would be best answered here, since I'm just looking for algorithms at the moment. I'm generating clouds on the fly, but I'm not ...
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
388 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
99 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
543 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
59 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
274 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
78 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
59 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
113 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
129 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
14 views

Non-linearity on Random Sequence

I recently incorrectly assumed that applying a non-linear operation on a completely uncorrelated sequence would yield an uncorrelated sequence. Turns out that it is trivially easy to show that this ...
1
vote
0answers
12 views

How to find covariance matrix from correlation if mean is not given?

I'm given autocorrelation function of gaussian random process: $$ R_x(\tau) = 3e^{|-\tau/3|} $$ Now I should find covariance matrix. I know the formula and solutions, where $$ C_{xx} = R - E[X]E[Y] $$ ...
1
vote
0answers
39 views

Distinct pairs formed using repeated sequences

Problem setting: Let $N$ and $M$ be positive integers. Let $I'$ and $J'$ be ordered sets, i.e., sequences, $\{1,2,\ldots,N\}$ and $\{1,2,\ldots,M\}$ , respectively. The sequences are $N$ and $M$ in ...
1
vote
0answers
15 views

Calculation of arrival time of messages from 1 source through 2 different routes

I need to simulate sending messages from $A$ to $B$ as follows: Each message is sent $N$ times from $A$ on the same time, passes through a certain route $R_n$ and arrives at $B$. Travel time of $R_n$ ...
1
vote
0answers
26 views

How many shuffles are really needed for bridge?

According to the Gilbert-Shannon-Reeds model (which apparently models reality well), one should riffle shuffle seven times to achieve a suitably randomized $52$ card deck. However, it occurs to me ...
1
vote
0answers
17 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
22 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
66 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
30 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 ...