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

learn more… | top users | synonyms

7
votes
0answers
151 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
802 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
0answers
93 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
333 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 ...
5
votes
0answers
202 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
1k 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: ...
4
votes
0answers
50 views

Shuffle Deck $7$ times or $8.55$ times?

Persi Diaconis showed in $1992$ that in order to shuffle a deck of $52$ cards, you need at least $7$ riffle shuffles. However, in the paper he published, he showed that we needed ...
4
votes
0answers
55 views

What is the difference between random variable and uncertainty?

Please help me to find the difference between random variable and uncertainty? Can use the formula for the area of random variables (expectation, derivation,...)in the field of nonrandom variables ...
4
votes
0answers
133 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 ...
3
votes
0answers
44 views

How to punish a riffle shuffle?

It is common knowledge that for a deck to be considered randomly sorted, at least seven riffle shuffles should be used. However, in my experience, very few people will take the time to complete seven ...
3
votes
0answers
51 views

Random Numbers and probability

How long does a sequence of random decimal digits (0, 1, 2, ..., 9) need to be before you can "reasonably" expect the sequence to contain all numbers from 0 through 999 (inclusive). -- It's up to ...
3
votes
0answers
46 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
100 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
43 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
77 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 ...
3
votes
0answers
43 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
680 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 < ...
3
votes
0answers
62 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
87 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 ...
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
757 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
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 ...
2
votes
0answers
31 views

Limiting distribution of infinite sum of weighted bernoulli?

Let $p_n$ be some fixed pulse, for example $p_n =e^{-n^{2}}$ We have an infinite sum $y = \sum_{n=-\infty}^{\infty} a_n p_{-n}$ where $a_n$ are iid bernoulli random variables taking the values $+/- ...
2
votes
0answers
42 views

What's the name of this extremely common but extremely pathological continuous function?

Okay, so let's define a random function $F$, such that the value of $F(x)$ is uniformly distributed on $[-1,1]$, and such that for any $x$ and $y$ with $x \ne y$, $F(x)$ and $F(y)$ are independent. ...
2
votes
0answers
41 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
39 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 ...
2
votes
0answers
28 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
46 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
24 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
83 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
72 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
142 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
209 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
107 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
102 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
150 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
228 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
66 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
79 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
110 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
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
323 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
62 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
128 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
101 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
35 views

discrete random variable with uniformely distributed random variable

I hope you can help me because I have no clue where to start: Let X be a discrete random variable with $ p_k=P_X[X=x_k]=p(x_k) $for all $1\le k\le N$ for $N\in \Bbb N$ and distribuition function: ...
1
vote
0answers
32 views

Is a “deterministic” subset of a random subset random?

Let $S$ be some set and consider $X \subseteq S$ of size $|X|=x$ u.a.r. (among all the subsets having this size). Now, use some properties of this set $X$ to find some subset $Y\subseteq X$ of some ...