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

learn more… | top users | synonyms

6
votes
0answers
37 views

Generating a Random Connected Graph

Given a graph G(V, E), with |V | = n and |E| = 0 (that is, the graph is empty), and a static set F containing all the possible edges. Consider the following algorithm for generating a random graph. ...
6
votes
0answers
80 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 ...
6
votes
0answers
591 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
118 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 ...
5
votes
0answers
258 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
63 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
114 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
857 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
28 views

How to sample from a convex hull?

Let us consider a couple of points $x^{(i)}\in \mathbb{R}^m$ where $i=1,\dots,n$. Convex hull is defined as $$ C = \left\{\sum_{i=1}^{m} \alpha_i x^{(i)} \mathrel{\Bigg|} (\forall i: \alpha_i\ge ...
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
63 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
41 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
60 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
624 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
951 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
29 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
17 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
37 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
69 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
63 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
70 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
111 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
147 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
44 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
96 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
86 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
151 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
395 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
101 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
548 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
283 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
79 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
60 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
115 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
11 views

the meaning of 4-wise hash function

If someone says: 4-wise independent sign (hash) functions $s_1,s_2, s_3 : [d] → \{+1, −1\}$, then what does it means? I cannot use k-wise Independence variables (the definition 1 ...
1
vote
0answers
27 views

Is the Library of Babel random? Does it contain information?

The Library of Babel is defined as a universe in the form of a vast library containing all possible 410-page books of a certain format and character set. However, applying two means of ...
1
vote
0answers
15 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
14 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
51 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
18 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$ ...