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

learn more… | top users | synonyms

0
votes
0answers
8 views

Why Real and Imaginary parts of a field in k-space are uncorrelated

I am in the process of generating a (real) Gaussian random field $\delta(\vec{x})$ from a given power spectrum $P(k)$. The way I define the power spectrum is, in Fourier space, $\left\langle ...
1
vote
0answers
10 views

Select a random edge [on hold]

Given a source of random bits and a multigraph G(V, E), provide an algorithm for selecting an edge e ∈ E uniformly at random in O(n) time.
5
votes
0answers
26 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. ...
0
votes
0answers
52 views

Disjoint increments of Poisson mixture process are memory-less

Let $N(t)$ be a Poisson mixture process: $$N(t) \sim (1-p) \cdot \text{Poiss}(\lambda_0 \cdot t) \: + \: p \cdot \text{Poiss}(\lambda_1 \cdot t),$$ where $p$ is fixed and $0<p<1.$ As we ...
4
votes
3answers
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 ...
0
votes
1answer
26 views

uniform distribution vs normal distribution for discount use case [on hold]

Problem statement: Reward a customer with lucky draw coupon of X% discount in between 1% to 100% Assume that slabs are pre-defined ( all are theoretical) 1% discount : 90% customers 10% ...
-1
votes
1answer
38 views

LCM of randomly selected integers

What is the expected LCM of 21 randomly selected positive integers under 10000000? How would someone even approach this problem? EDIT: The positive integers are chosen with replacement.
1
vote
1answer
296 views

Compressing random numbers

I've been thinking about ways to compress the output from a (supposedly) random number generator. Let's assume for a moment that my computer can produce high-quality random numbers. I'm certainly not ...
2
votes
1answer
20 views

Is $a+r \cdot b$ an uniformly random value when $a,b$ are fixed and $r$ is random value?

Imagine we have two fixed values $a,b \in \mathbb{Z}_p$ and a uniformly random value $r\leftarrow \mathbb{Z}_p$, for large prime number $p$. Question: Is $v=a+b\cdot r$ an uniformly random value in ...
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 ...
-2
votes
1answer
32 views

Probability of 2 integers selected are the same is greater than 0.7 in random generated set of 14 intergers. [closed]

A set of 14 random generated integers between (inclusive) 10-30 are generated (repetition is allowed, meaning that it is possible of 2,3 or more random generated integers are same), how many number of ...
2
votes
1answer
379 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 ...
1
vote
2answers
41 views

What is the probability that at least one 10 day period contains 6 birthdays if there are 60 birthdays throughout a year?

For all possible contiguous 10 day periods within a single calendar year, what is the probability that at least one of the 10 day periods contains six birthdays if there are 60 birthdays randomly ...
0
votes
1answer
21 views

Nonlinear transform of two random variables for Gaussianity

I would like to understand the nonlinear transform of Gaussian random variable that preserves Gaussianity better when there is no $x_3$ term such that there exists a nonlinear relationship between ...
0
votes
0answers
31 views

mathematical expression for randomely selecting from two integers

I want wondering what is the shortest and correct mathematical expression for the below: $x =$ random$(1$ or $2)$ where there is equal probability of selecting 1 or 2. Thanks for your help.
0
votes
0answers
18 views

mathematical notation for random selection of two integers

I want the shortest mathematical notation for the below: $x =$ random$(1,2)$ where there is equal probability of selecting 1 or 2. is it correct to state: $x \sim$ U$(\{1,2\})$. If I had more ...
0
votes
0answers
14 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 m $$ where $m$ is prime (for concurrency reasons). However, the ones I have found in the literature either have ...
0
votes
1answer
64 views

Partially Identical Hands in Hold'em

I was playing Texas Hold'em at a local cardroom last night keeping a meticulous record of the hands I was dealt. Perhaps I am totally wrong but I thought the occurrences of certain events in this ...
0
votes
1answer
45 views

Stat: Probability to have one element of a combination identical to one element of another combination

For a business application, I currently have to provide the probability we are going to have an issue in one application. The combination is composed of N unique ...
8
votes
3answers
2k views

What is golden ratio doing in this computer code?

In this file (related to random number generation), there is following line: private const int MSEED = 161803398; which resembles golden ratio. How come ...
3
votes
0answers
46 views

independence of x/y and y given that x and y are not independent [closed]

Suppose two non-negative random variates x and y are NOT independent (in my case that I am interested in, the range of x is constrained by y, i.e., $0<x\leq y$). In more specific, assuming $y$ ...
0
votes
2answers
34 views

Choosing something 35% more often

If I want to select an element from an array at random, the following will choose each element roughly at 1/L percent of the time: ...
0
votes
1answer
19 views

Apportioning 100% across 24 hours

Assume I have value x=500. I would like to apportion this value 500 across 24 hours time period and would like it to be apportioned randomly. So if 500 is 100% the x% generated at random would be used ...
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 ...
0
votes
0answers
12 views

Convergence random matrix inverse

I have the following problem: A is a sum of independent random matrices that converges in expectation to say a matrix C and B is some fixed positive (semi-)definite matrix. I'm interested in a bound ...
5
votes
2answers
133 views

Do you need true randomness to beat the two-envelope game?

A well-known (non-)paradox in probability involves a two-envelope game played between two players, $A$ and $B$: $A$ selects two distinct (real) numbers, $x$ and $y$, writing each one down on a card ...
2
votes
3answers
37 views

Expected amount of repeats in a random sequence of integers

I'm looking at a series of random integers generated by a CSPRNG and noticed that there are more repeats (that is a number is in the sequence 2 or more times e.g. 9,3,8,5,6,3 - 3 is a repeat) than I ...
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 ...
2
votes
3answers
68 views

Can you get a fair coin flip by rolling a fair, 5-sided die a finite number of times?

Can you get a fair coin flip by rolling a fair, 5-sided die a finite number of times?
0
votes
1answer
37 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$, ...
3
votes
1answer
45 views

Find probability of a Poisson process.

Given that $N=\{N(t)\mid t\geq 0\}$ is a Poisson process with parameter $\lambda>0$ I need to find $P(N(3)=2\mid N(1)=0, N(5)=4)$ So this is a conditional probability (can anyone clarify if this ...
20
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 ...
0
votes
1answer
20 views

Which is the probability?

On the Swedish SAT test, you have 5 options for every question where precisely one option is correct. If you answer randomly, what is the probability that your score will be 0.9 if the maximum score ...
5
votes
1answer
711 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 ...
2
votes
1answer
36 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) ...
2
votes
3answers
48 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
55 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 ...
1
vote
1answer
41 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
16 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
27 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
15 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
70 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
103 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)$ ...
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
19 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 ...