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

learn more… | top users | synonyms

1
vote
2answers
40 views

Kth largest element from N chosen with a non-standard distribution

I have the following problem: $n$ values $U_1, \ldots, U_n$ are chosen randomly and independently from the interval $[0,1]$. When choosing $U_i$, the probability that $U_i$ is smaller than a ...
3
votes
3answers
65 views

Looking for strictly increasing integer sequences whose gaps between consecutive elements are “pseudorandom”

I am doing some tests with strictly increasing integer sequences whose gaps between consecutive elements show a "pseudorandom" behavior, meaning "pseudorandom" that the gaps do not grow up ...
0
votes
2answers
46 views

How to calculate the average number of guesses made to guess a number between 0 and 31?

I know this question is very basic, but my question is more about Mathematical thinking. How to think mathematically: Suppose person $A$ chooses a number from numbers between $0$ and $31$, and ...
0
votes
0answers
20 views

Complexity of a randomly-traveled N*M grid

I made an algorithm that compute a random-path across a N*M grid using backtracking. It start at [N / 2][0] and shall finish at [N / 2][M - 1]. Each iteration he choose a random direction (Left, Right,...
2
votes
2answers
98 views

Is there a way to mathematically prove my teaching assistant is wrong?

Our design of algorithms class requires all students to enroll in an online $AI$ competition, where each team has to come up with a bot. Before the final lockdown, each team is allowed to challenge ...
1
vote
1answer
60 views

PDF of maximum of two random variables

X and Y have joint PDF $$\ f_{X,Y}(x,y) =\begin{cases} 1/15 & 0\le x \le 5, & 0 \le y \le 3 \\ 0 & \text{otherwise.} \\ \end{cases} $$ Find the PDF of $W = max(X,Y)...
0
votes
0answers
31 views

How can you distinguish modular exponentiation from random?

Let $N$ be the product of two primes and let $P$ be the smallest prime larger than $N$. Let the algorithm $R(N,s)$ return $s^{1/P} \pmod{N}$. Let the algorithm $\widehat{R}(N,s)$ pick a ...
1
vote
2answers
50 views

What is $cov(XY,X)$

Suppose I have two real valued random variables $X$ and $Y$. Let $cov(\cdot)$ denote the covariance operator. What is $cov(XY,X)$? Is it zero if $cov(Y,X)=0$?
0
votes
0answers
19 views

How to find COV(max(a,b),max(c,d))?

We have normal random variables with nonzero mean, $$ X_i \sim N(\mu _{x_i},\sigma^2 _{x_i}) $$ $$ Y_i \sim N(\mu _{y_i},\sigma^2 _{y_i}) $$ $$ Z_i \sim N(\mu _{z_i},\sigma^2 _{z_i}) $$ They are ...
1
vote
5answers
256 views

If I ask $1000$ people to choose a random number between $0$ and $999$, what is the probability that no one will choose a specific number?

Imagine I asked $1000$ people to choose a number between $0$ and $999$ (both inclusive, the numbers are not biased, they will be completely random) and write that number down. Now, after that, pick a ...
1
vote
1answer
27 views

are all the variables independent of each other

Consider three random variables $X, Y$ and $Z$. If $X$ and $Y$ are independent, $Y$ and $Z$ are independent, then does that mean that $X$ and $Z$ are independent too?
0
votes
1answer
67 views

What is the probability that more passengers will turn up for a flight than the aircraft has the seating capacity for?

Daily Airlines flies every day from Amsterdam to London. The price for a ticket on this popular route is \$75. The aircraft has a capacity of 150 passengers. Demand for tickets is greater than ...
60
votes
3answers
1k views

Mathematicians shocked(?) to find pattern in prime numbers

There is an interesting recent article "Mathematicians shocked to find pattern in "random" prime numbers" in New Scientist. (Don't you love math titles in the popular press? Compare to the source ...
3
votes
2answers
86 views

Probability: Store opening time

Smith has a small booth where he sells lottery tickets. Customers arrive according to a Poisson process of rate $\lambda$= 1 per minute. He will close the shop on the 1st occasion that $a$ minutes ...
0
votes
0answers
20 views

Skewness and Kurtosis Excess, maximum allowed deviation for randomly generated numbers

I'm programming a random number generator which generates numbers according to a user-specified probability distribution (Bernoulli, exponential, uniform, pareto, etc). To verify the correctness of ...
1
vote
1answer
106 views

Mixture process conditioned on another mixture process

Let $N(T_1)$ is Poisson counting mixture process and $M(T_2)$ is another independent Poisson counting mixture process, such that $$ N(T_1) \sim (1-p) \cdot \operatorname{P}(\lambda_0T_1)+p \cdot \...
0
votes
1answer
20 views

Plotting a random but continuous line

Hopefully my question makes sense. I would like to generate a function which is continuous at all points. The use of the word "random" is somewhat of a misnomer, since it is not truly random. It must ...
1
vote
0answers
27 views

Delta Method: Estimate the Variance of $T$

Let $X = (X_1,\ldots,X_n)$ be a random sample, where $X_1 \sim \mathrm{Bern}(p)$. Let $\lambda = e^p$. Question: By law of large numbers, $T=e^{(\bar{X})}$ is a consistent estimator for $\lambda$, ...
1
vote
1answer
33 views

A random invertible matrix

I work on a project, for these project i need to generate a square random invertible matrix. I found out how to generate a square random matrix, still i want to be sure that this is an invertible one,...
0
votes
1answer
29 views

significance of a test for (javascript) pseudo-random generator

I wrote a test case that tests if the javascript pseudo-random number generation algorithm of a given implementation has a given number of significant bits. You can see and test my code here: https://...
2
votes
1answer
59 views

the greater of two random variables

For two independent normal random variables with non-zero mean $$ X \sim N(u_1,\sigma_1) , Y \sim N(u_2,\sigma_2) $$ If we have the condition, $$E(X^2 ) > E(Y^2)$$ is this condition always ...
0
votes
0answers
13 views

maximizing over variable with random variable as upper bound

Let X be a random variable. Does the following hold: $$ \max_{g\in(0.2,0.3)}(P(X>g)+P(X\leq g))\leq \max_{g\in (0.2, X)}P(X>g)+\max_{g\in (X,0.3)}P(X\leq g)$$ The separate maximization is clear ...
12
votes
1answer
177 views

Fitting a parabola to separate two classes of points in the plane

Suppose we have a set of points $(x,y)$ in the plane where each point is either boy or a girl. Does there exists a randomized linear-time algorithm to determine if we can fit a parabola (given by a ...
0
votes
2answers
205 views

Monkey typing keys probability formula [closed]

A monkey is sitting at a simplified keyboard that only includes the keys “a”, “b”, “c”, and “d”. The monkey presses the keys at random. How many sequences are there of length eight that use at most ...
1
vote
1answer
63 views

What is the formal definition of randomness?

What is the formal definition of mathematical randomness? For example, if one were to prove that a random number generator is random, how would one go about constructing a proof?
4
votes
1answer
249 views

When is random selection skewed (untrustworthy)?

Imagine there is a population of 100 people, out of which 3 are to be randomly selected each day for alcohol testing. After a month of such selections (after 20 selections), how many times somebody ...
1
vote
0answers
34 views

If you resize a pink noise image, will the pink noise be preserved?

I have a pink noise image of e.g. 500x500 resolution. If I resize the image to a new size with imresize, will the resulting image be pink-noise or will it be something close to it, but not the same? ...
1
vote
0answers
35 views

Expectation of product of matrices

Let $H$ be a random matrix, and $x$ be a random vector with $E[xx^{H}]=R$. They are independent. I want to calculate $E[Hxx^{H}H^{H}]$, where $A^{H}$ is a Hermitian of $A$. Does the equation $E[...
0
votes
0answers
14 views

Singular vectors of random Gaussian matrix

Let $A$ be a singular vector matrix of a random Gaussian matrix. The entries of the Gaussian matrix are i.i.d., so the singular vectors are distributed isotropically. Is it possible to get $E[AA^{H}]$?...
0
votes
1answer
24 views

Generating a deterministic random function that takes into account the date as well as a long ID

In SQL Server there's a function RAND() that if you pass a seed to it will return a pseudo random number based on the seed. No matter when you pass that same seed into this function, it will always ...
1
vote
0answers
46 views

What does it mean for a sequence of random variables to be increasing?

According to a textbook I'm reading, one statement of the monotone convergence theorem is: If $X_1, X_2, ...$ is a sequence of non-negative random variables increasing to the random variable $X$, ...
-1
votes
2answers
35 views

What random variable is this?

I have a sequence of reals $S = s_1,s_2,\dots,s_n$ such that $s_i-s_{i-1}$ is a Gaussian distribution. From histogram of sequence $S$ (10000 elements) it appears that it is uniform distribution. Is it ...
0
votes
0answers
13 views

Prove that the mean of the $u_i$'s generated by a congruential linear generator of complete period is $\frac{1}{2} -\frac{1}{2m}$

Congruential linear generator (pseudo random numbers) I have to prove this proposition but I don't know how. I tried by induction on $m$, the modulus of the generator, but it hadn't got me anywhere: ...
1
vote
1answer
53 views

Attempt to solve a matrix (counterbalancing) problem computationally gives “spooky” result: why?

This question is posted on the mathematics section of stackexchange because my uneducated guess is that the answer involves some basic mathematical principles, possibly in the domain of linear algebra....
1
vote
1answer
97 views

Ms. A selects a number $X$ randomly from the uniform distribution on $[0, 1]$. Then Mr. B repeatedly, and independently, draws numbers. [closed]

Ms. A selects a number $X$ randomly from the uniform distribution on $[0, 1]$. Then Mr. B repeatedly, and independently, draws numbers $Y_1, Y_2, ...$ from the uniform distribution on $[0, 1]$, until ...
0
votes
1answer
27 views

Random sum of normal distribution with bounds Poisson distributed?

A random variable, $M$, is Poisson distributed with $\lambda=2$. ${X_1,X_2,\dots}$ are independently identically distributed random variables with $\mu=3$ and $\sigma=.2$. Introduce a new random ...
0
votes
0answers
18 views

Is there any trick for evaluate this integral?

Does the following function can be simplified or solved? $$R(i) = \int_{y\in S} {\frac{{w(y) g(y,i)_{}^\sigma }}{{\int_{x\in S} {h(x)g(x,y)_{}^\sigma f(x,y)_{}^\sigma dx} }}dy} $$ where S is a ...
1
vote
2answers
41 views

Calculating first and second moments for random sums?

Assume that $N$ and $X_1, X_2, \ldots $ are all independent and identically distributed over $(0,1)$ with the density function: $f (x) = cx^2 (1 − x)^2$. An integer–valued random variable, $N$ ...
0
votes
0answers
10 views

Statistical distance between a multiplicative mask and a random number

Given $x \in \{1,\ldots,2^n\}$ and a uniform random $r \in \{1,\ldots,2^{n+k}\}$, then the statistical distance $\Delta(x + r\bmod q; r) < 2^{-k}$, for a $q > 2^{n+k+1}$. With addition this is ...
0
votes
2answers
33 views

What is the probability or percentage or frequency by which hello line will be printed?

I have a below method which is called every one minute from background thread and that background thread keeps running always. ...
0
votes
0answers
58 views

Random selection in percentage

I have $3$ lists of things. I want to choose things randomly from this lists. But have percentage limitation on the lists. Like I can select only $60$% things from $1$st list, $30$% from $2$nd list &...
0
votes
0answers
16 views

Switching blinding factors securely.

My question is related to information security area and I have asked almost a similar question in: http://crypto.stackexchange.com/questions/32427/secure-blinding-factor-switching-at-malicious-server-...
0
votes
0answers
62 views

Euclidean norm of two random variables

I have two normally distributed random variables. $X_1$ and $X_2$ with mean $u_1,u_2$ and variance $s_1^2,s_2^2$. They are independent with each other and have interval $(-\infty,\infty)$. Is it ...
2
votes
1answer
91 views

Measure of card shuffling randomness

I've read online that you need to shuffle a deck of cards at least 7 times (depending on the game being played) for the deck to be 'random enough', i.e. that it is nearly impossible to predict the ...
1
vote
0answers
39 views

Is it possible generate all integer number (from 0 to 2147483647 ) randomly without repetition

From a mathematical point of view it's possible do what I wrote in the title? In computer science I could resolve the problem creating an array which contains all value from 0 to 2147483647 and then ...
0
votes
1answer
26 views

ideal number gernerator

I was trying to solve a problem on Hackerearth. Here: https://www.hackerearth.com/problem/algorithm/ideal-random-number-generator/ I solved this partially:https://ideone.com/pXkHwQ (passed three cases)...
2
votes
2answers
114 views

Baseball related problem (balls and boxes)

Thanks in advance for any help! So I am trying to figure out if the number of hits an inning of baseball is random, or if hits tend to come in bunches. To do this, I'm just using a fairly small ...
0
votes
0answers
28 views

Expected Number of Cycles in Random Permutations with a Random Number of Symbols

It is known that for permutations sampled uniformly from $S_k$ that $\mathbb{E}[C] = H_k = O(\log k)$ (more precisely, $\Theta(\log k)$), where $C$ is the number of cycles in a random permutation. If ...
0
votes
1answer
24 views

How would I go about calculating values for distributed percentages?

This might be really simple, but I just can't see it. I'm working on a game that has 8 items each with a (arbitrary) probability (% chance) of being found: ...
0
votes
0answers
29 views

Random process theory: probability distribution of height vs summits

Imagine I have a matrix of height values ($z$), e.g. a surface height topography. This surface is a random process: randomly rough isotropic surface with Gaussian distribution. What is the difference ...