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

learn more… | top users | synonyms

5
votes
1answer
696 views

Mapping random points on a sphere onto a uniform grid

Say I had an arbitrary sphere that is covered in a uniform triangle mesh of N elements with each element having a unique sequential index. If given the coordinates of a random point on the surface of ...
15
votes
3answers
2k views

Choose a random number between 0 and 1 and record its value. Keep doing it until the sum of the numbers exceeds 1. How many tries do we have to do?

Choose a random number between 0 and 1 and record its value. Do this again and add the second number to the first number. Keep doing this until the sum of the numbers exceeds 1. What's the expected ...
19
votes
5answers
2k views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
2
votes
1answer
27 views

Intuition on Martin-Löf-Test for finite strings

The followng example is from An Introduction to Kolmogorov Complexity and Its Applications, Example 2.4.1. and is concerned with Martin-Löf-Tests for finite strings: A string $x_1 x_2 \ldots x_n$ ...
4
votes
3answers
2k 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. ...
1
vote
2answers
22 views

Show that $Cov(X,Y) \geq -23$

if $X,Y$ are two random variables and: $Var(X) = Var( Y) = 23$ how can i show that $Cov(X,Y)\geq -23$ can someone give me some hints on how to show it?(not an answer) i know that $Cov(X,Y) = E(XY) ...
0
votes
1answer
27 views

Partition-based entropy of a sequence

The entropy $H$ of a discrete random variable $X$ is defined by $$H(X)=E[I(X)]=\sum_xP(x)I(x)=\sum_xP(x)\log P(x)^{-1}$$ where $x$ are the possible values of $X$, $P(x)$ is the probability of $x$, ...
1
vote
3answers
42 views

Intuition behind generating continuous random valiables

If we have a random variable $X$ with cumulative distribution function $F$ that is strictly ascending and we manage to find the inverse we can generate an instance $x_1$ from a uniformly distributed ...
2
votes
1answer
361 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
2
votes
1answer
54 views

Bound on the probability that noise changes the majority value of random bits

I have the following problem. I have a vector of size $N$ in $\mathbb{F}_2$ containing exactly $m$ zeros and $n$ ones with $m>n$. Then, a random noise is applied on each bit independently such ...
2
votes
2answers
1k views

What does relaxing the iid assumptions mean? Intuitive and technical perspectives.

I believe the most restrictive assumption we can place on a series of observations is that they are iid. It is possible to relax these assumptions. For example relaxing the independent distribution ...
1
vote
1answer
36 views

Generate random number according to any equation

So I'm after a random number generator where the probabilities of a number occurring in some range is matched to some function. Only really looking at functions with nice integrals (for simplicity ...
0
votes
0answers
14 views

continuous random variable - pth percentile

Let X be a loss random variable with cdf $$ F(x) = \left\{ \begin{array}{ll} 1-(θ/θ+x)^α & \textrm{for $x≥0$}\\ 0 & \textrm{for $x<0$}\\ \end{array} \right. $$ The 10th percentile is θ−k. ...
3
votes
0answers
23 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 ...
1
vote
1answer
30 views

Shuffling the columns of a matrix

Suppose I have an $N\times k$ matrix: $$\begin{bmatrix}a_{1,1} & \cdots & a_{N,1} \\ \vdots & \ddots & \vdots \\ a_{1,k} & \cdots & a_{N,k} \end{bmatrix}$$ Is there a ...
0
votes
0answers
13 views

Is two single byte random codes more secure than a single word random code?

I am trying to create secret keys for a post so users can edit them without entering password. Typically I use two secret IDs to reference a post, ID1=8 byte long random code ID2=8 byte ...
3
votes
2answers
63 views

A single, good test for a random number generator?

I'm chasing a bug in the RNG for a well-known programming language under certain pathological inputs. There is an obvious pattern in this pathological case, apparent with very small n (~ 10000), and ...
0
votes
1answer
30 views

Hitting all bins at least once

$m$ balls are thrown at a total of $n$ bins. Each ball will fall into exactly one randomly chosen bin with each throw. What is the probability that each bin is hit at least once (contains at least one ...
2
votes
1answer
93 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)$ ...
6
votes
0answers
73 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 ...
0
votes
1answer
22 views

Uniform random number generation

Given a uniform random number generator that generates integers between any given range, a n-tuple $b$, and an integer $c$, how can one uniformly generate n-tuples ($x$) that meet the following ...
0
votes
0answers
15 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
1
vote
1answer
46 views

Randomness in pi and other irrational numbers [duplicate]

This is a post I read about pi while looking for stuff about tau -which is two times as much as pi. This makes me wonder, why does only pi contain such randomness? Don't other non-repeating and ...
2
votes
0answers
27 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 ...
1
vote
4answers
56 views

The normal distribution is a common model of randomness

Can someone please comment/elaborate on the statement: "The normal distribution is a common model of randomness." I would like to understand it more deeply. Source: Perhaps someone can point me ...
0
votes
2answers
39 views

Worst case binary search

Suppose you play a game with a computer program where you guess a number between 0 and 1 and the computer uses binary search to search for your number. My question is what is the best number to ...
0
votes
0answers
9 views

How to define a one-parameter family of probability distributions

I am trying to evaluate a noise-source as a means of providing entropy to a random number generator. I am running into trouble when it comes to determining the probability distribution that has the ...
0
votes
2answers
59 views

Random equation-does it make sense?

What is the probability that the equation $$x^2+2bx+c=0$$ has real roots? Answer is exactly $1$. (or $100$%) For example: if $b=1$ and $c=2$ roots are complex. Does it make sense? If $P(A)=0$, then ...
7
votes
3answers
120 views

Random Sequence of Alternating Increase/Decrease Numbers

The problem statement: Repeatedly pick a random number (uniformly-distributed) between $0$ and $1$. Keeping going while the second number is smaller than the first, the third number is larger than the ...
0
votes
0answers
9 views

Can PRNGs and RNGs work as different RNG/PRNGs?

I think the title was pretty bad but I'll explain. Let a RNG-n and a PRNG-n be a random integer generator and pseudo-random integer generator respectively that both randomizes integers from 1 to n (1 ...
1
vote
2answers
64 views

How many bit-flips are required to achieve random distribution?

If I have a binary number W bits wide, initially all set to zero, and I repeatedly pick a random bit and toggle it from zero to one or vice versa, how many times would I need to do this to achieve ...
19
votes
7answers
5k views

Generate a random direction within a cone

I have a normalized $3D$ vector giving a direction and an angle that forms a cone around it, something like this: I'd like to generate a random, uniformly distributed normalized vector for a ...
1
vote
1answer
12 views

Dynamic weighed probability

If I have a list of objects, and want [programmatically] to randomly pull one out, I can simply choose a random number representing a valid index within the range of elements of the list: ...
2
votes
2answers
43 views

Can this probability mechanic be used in a simulated gambling scenario?

This question is a bit complicated, so please bear with me. I realized this question after watching this video from the popular Youtube channel Numberphile. This video claims that when two random ...
2
votes
1answer
32 views

Unknown random number generator

I recently browsed through someone else's code and found a section where a pseudo random number generator is implemented. I know that random number generation is not an easy task, some even regard as ...
0
votes
0answers
8 views

Linear congruential generator, $\pmod p$ a prime

I'm interested in pseudorandom generators of the kind $$ x_n = a\cdot x_{n-1} + c \pmod n $$ where $n$ is prime (for concurrency reasons). However, the ones I have found in the literature either have ...
0
votes
1answer
22 views

Randomization and probability with constraints

The probability of getting a specific suit out of a deck is 13/52. Once we have one suit (color) selected the probability is 12/51 for that suit and 13/51 for others. This much is obvious. Now ...
6
votes
1answer
91 views

What is a formal definition of 'randomness'?

What is a rigorous mathematical/logical definition of 'randomness'? Under what conditions can we truthfully apply the predicate 'is random'?
1
vote
1answer
13 views

Random Numbers and Binomial Distribution

Let's say we have generated n=100000 numbers from a set: {1, 2, ..., 50}. Let X a discrete random variable that expresses the number that 1 appears. Then X~Binomial(n,p), where n=100.000 and p=1/50 ...
2
votes
4answers
84 views

What is the statistical equilibrium for this simulation of happy bubbles?

Happy Bubbles I hope this is not too specific or practical, but I just made a simulation of sorts and seem to have hit quite close to an equilibrium (by accident). Now I am wondering if and how you ...
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 ...
0
votes
2answers
32 views

Random 4D vector

I'd like to generate random 4D vectors. Their length must be 1. A random 2D vector can be created like so: ...
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] $$ ...
2
votes
1answer
28 views

What was the paper about flower-shaped knots?

I read a article about the possibility to bring knots in a "polar rose" projection, where there is only one crossing of higher multiplicity. The overcrossing/ undercrossing information is thus more ...
0
votes
0answers
30 views

a sequence of integers associated to a bernoulli process

Is it possible to associate a sequence of integers to a Bernoulli process such that for every trial an integer is chosen and the average of the integers associated to the successes is twice the ...
0
votes
0answers
68 views

Confusion about a random process

Let $X(t)$ be a random process such that: $$ X(t) = \begin{cases} t & \text{with probability } \frac{1}{2} \\ 2-at & \text{with probability } \frac{1}{2} \\ \end{cases}, $$ where $a$ is a ...
1
vote
2answers
60 views

Random Uniformly Distributed Points in a Circle

I know that by just using a random angle and a random radius within the bounds of your circle, you will end up with points near the center of a circle. Whereas if you do ...
-3
votes
1answer
92 views

Variance of a special random walk

I am trying to find the variance of the following special random walk: Suppose that $U=(U_1,U_2,...)$ is a sequence of independent random variables, each taking values $u$ (for up) and $d$ (for down) ...
20
votes
7answers
9k views

What's the difference between stochastic and random?

What's the difference between stochastic and random? I've read in the portuguese wikipedia that there's a difference, but I still didn't see this point on english wikipedia.
1
vote
0answers
44 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 ...