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

learn more… | top users | synonyms

1
vote
0answers
16 views

Replacement for bitwise XOR on GPU for combining hashes and randoms

Bitwise XOR is often used for combining hashes or random number generators (http://math.stackexchange.com/a/340028/266666). This operator has a good property: if r1 and r2 are uniformly distributed ...
3
votes
1answer
99 views

Expected number of steps - shuffling a sequence

I've been struggling with a problem a CS student friend of mine gave me a few hours ago. Given that $P$ is an array of integers and $N$ is its size, how many minutes is the following algorithm ...
1
vote
2answers
30 views

Permutations in an Infinite List of Random Numbers

In an infinite list of random numbers from a to b, prove that in this list, there are all possible permutations of n numbers from the list, where n can be any number. Here are some versions of the ...
1
vote
0answers
33 views

Scrambled Sobol

I need to do a Monte Carlo simulation in high dimension (up to 1000) where using plain Sobol (with Kuo's direction vectors) as a random number generator is not good enough. Therefore I am ...
0
votes
1answer
32 views

Test to determine whether a huge series of integers is random or there is a pattern?

I have a series of integers in which some integers occur more than others. I want to know if there is a test to determine whether these integers are randomly distributed or some integers occur more ...
3
votes
2answers
52 views

Determine whether a random binary sequence was generated by human or natural process

Given a binary sequence, how can I calculate the quality of the randomness? Following the discovery that Humans cannot consciously generate random numbers sequences, I came across an interesting ...
0
votes
1answer
40 views

How large must be the sample to determine the probability of a binary outcome?

Suppose a computer program randomly generates a "yes" or "no" answer upon request. You however do not know whether the probability of getting either answer is evenly split or following a different ...
0
votes
1answer
47 views

How to simulate a delta-correlated random process

I'm trying to do the simulation described in the paper attached, but there is something I don't understand. The author says that the random variables which satisfy the relation (Eq. (4) in the paper) ...
3
votes
1answer
35 views

Number of random guesses needed to guess a number in a given set [duplicate]

I am not very good with probability theory and related stuff, so I would very much appreciate your help regarding a problem I have. Imagine arbitrarily picking an integer $n\in [1,N]$ I want to ...
-9
votes
2answers
56 views

Are these numbers random? [closed]

Are these numbers random? If not, please give 2 reasons. $$0.001\ \ \ \ 0.002\ \ \ \ 0.003\ \ \ \ 0.004\ \ \ \ 0.005\ \ \ \ 0.006\ \ \ \ 0.007\ \ \ \ 0.008\ \ \ \ 0.009\ \ \ \ 0.01 $$
1
vote
0answers
19 views

Generating Failure rate function using Octave.

I'm not familiarized with programming using mathematics. My problem is described below. The lifetime T of a device has pdf Find the failure rate function. I have learned that Failure rate ...
1
vote
1answer
65 views

What is the average distance between two random points inside a circle?

Assume you have a circle with some radius r. What is the average distance between two random points inside the circle? (Edit: This is different from this already answered question, because here the ...
3
votes
5answers
76 views

Using the digits of $\pi$ to generate random numbers.

Let's say I've been captured by Russian operatives and am locked in a room with only one object: a book listing the digits of $\pi$. I'm told to generate a sequence of binary digits. If this sequence ...
1
vote
1answer
48 views

Terminology: is it random?

The topic of research of my master thesis is the use of probabilistic methods and models in music composition, particularly in the field of algorithmic music. As often is the case, artists tend to be ...
0
votes
0answers
61 views

Having rand2() function build rand5()

I was asked this question long time ago. Having a function $rand2()$ (in any computer language, "rand" means random) which returns $0$ or $1$ (two values only) with a uniform distribution, i.e. $$P(...
0
votes
0answers
7 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
0
votes
0answers
23 views

random binary sequence [duplicate]

Suppose we generate a sequence containing only 0's and 1's. We generate this binary string by randomly adding a 0 or 1 one at the time. We stop when the sequence contains k more 1's then 0's or k more ...
0
votes
0answers
52 views

Random walk visiting $k$ distinct points

I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact ...
1
vote
0answers
36 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: $$...
0
votes
1answer
43 views

Does this set of infinite binary sequences have positive probability?

The AMM article "What is a random sequence?" argues (at the end of Sec. 2) that if, from the set of all binary sequences, we remove those (countably many) that have "computable regularities", then the ...
0
votes
1answer
20 views

Probability of maximum of a random walk?

Let us consider a random walk denoted by Sn and let Mn be the maximums of the random walk. Now let us consider that this random walk will end at some point k. SO I am stuck how to prove this equality: ...
3
votes
0answers
45 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 ...
0
votes
0answers
23 views

Probability of the n-th dice matching in 2 groups of sorted random numbers

Say we have 2 groups of 6 6-sided dice. Each group of dice is rolled and then sorted so we have 2 groups of sorted numbers. What is the probability of each die in the group matching the corresponding ...
0
votes
1answer
32 views

Forced probability using a random number generator, mathematically correct or not?

What might happen if when using a random number generator, if a particular run is not so random, you "help it out" a little bit? For example, if we use a random number generator to simulate $10,000$ ...
0
votes
0answers
20 views

Arbitrary vs. random subsets: computing probabilities

Let $G=([n],E)$ be a graph having minimum degree $\delta(G) \geq (1-\delta) n$. For some $q=q(n)$, let $G_q=([n], E_q)$ be the random subgraph of $G$ obtained by deleting each edge independently with ...
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 (...
2
votes
2answers
67 views

Random and non-computable numbers

Let $\alpha \in (0,1): \quad \alpha=0.a_1a_2\cdots a_n \cdots \quad$ where the $a_n$ are numbers generated by a physical generator of genuinely random numbers (if it exists). Than it seems that $\...
3
votes
1answer
26 views

Is a subsequence of an exchangeable sequence exchangeable?

Consider a finite sequence of random variables $X_1,...,X_n$ (1) SUFF COND: Suppose $X_1,...,X_n$ are exchangeable, meaning that the joint probability distribution of $X_1,...,X_n$ is equivalent to ...
2
votes
1answer
96 views

Exchangeability and independence of random variables

I have a question on the relation between exchangeability and independence between random variables. Consider the random vectors $$u_1:= \begin{pmatrix} \epsilon_{1}\\ \epsilon_2\\ \epsilon_3 \end{...
0
votes
0answers
54 views

Particle in a box

Say I have a point particle located at the center of a box and imagine that I give it a velocity v in some direction. It will bounce back and forth in different directions maintaining the same speed |...
0
votes
1answer
10 views

Extending Random Number Ranges

I am provided with a random number $\xi \in [0,1]$. I check if a particular $\xi_i \lt x$ is true and if so, I need to convert those random numbers within the range $[0,x)$ into uniform range in $[0,1]...
0
votes
0answers
49 views

Sequence of non-independent coin tosses

Suppose that a sequence of coin tosses is due to be performed. Let $p_i$ denote the probability that the $i$th coin toss lands on Heads and let $X_i$ denote the corresponding indicator random variable ...
1
vote
1answer
15 views

Why does the average of a set of random numbers to the nth power approach 1/(n+1)?

I got bored and started running a Java program to mess with stuff like this. I did a boatload of trials and averaged them all together, first for a random number squared. Quick pseudo-code: ...
2
votes
1answer
26 views

Invertible Uniform “PseudoRandom” Function

Perhaps this is better suited to a cryptography stack exchange, but I thought I'd try in mathematics in case this question is more obvious than I initially thought. I'm looking for a function $~f:\{1,...
2
votes
0answers
36 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 $+/- \...
1
vote
0answers
39 views

Mean Value of a Random Process

Consider a random process $X(t) = Z(t)\sin(wt-Q)$. Here $Q$ is a random variable taking values $q$ in $[-\pi/2,\pi/2]$ with PDF given by $$p_1^Q(q) = \frac{\cos(q)}{2}$$ $Z(t)$ is some random ...
1
vote
1answer
50 views

Is there a statistical measure of bitwise entropy?

(Somewhat inspired by this website, particularly Section III. Also, I might be using a different definition of entropy than usual; what I am using is closest to the physics definition (the one I ...
1
vote
0answers
37 views

Practical example of superiority of randomized algorithm

I'm looking for an example to show my students of an algorithm for which randomization of some kind leads to better performance on average. And I don't want that randomization to be of the Monte Carlo ...
0
votes
0answers
26 views

Covariance matrix of random vector of vectors

I am a beginner in statistics and tried to research my question online without much success. Motivation: I am working on an undergraduate project in cosmology. My problem involves several scalar-...
0
votes
0answers
15 views

Using injective functions to prove randomness

Suppose we have a random subset of $\mathbb N$. My intuitive notion of randomness represents the ability to encode arbitrary real number. Assume that $A$ is a random subset according to the above ...
0
votes
0answers
3 views

How to calculate $E[P_e(Y)] = \int^\infty_{-\infty}Q(\sqrt {2y})f_Y(y)dy$

X is Gaussian (0,1) random variable with CDF $F_X(x)$ $$ Q(x) = 1-F_X(x) $$ Y is an exponential $1/\gamma$ random variable with PDF $$ f_Y(y) = \begin{cases} (1/\gamma)e^{y/\gamma} &y\ge0 ...
1
vote
2answers
39 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
44 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
96 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
58 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
30 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
47 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 ...