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

learn more… | top users | synonyms

1
vote
0answers
44 views

Probability of random functions where domain equals co-domain

Given random function defined by $f: [n] \rightarrow [n]$, chosen uniformly, what is probability that the function is injective, surjective, or bijective? If $[n]$ is a set of discrete elements, ...
2
votes
1answer
88 views

Probability of picked cards to be smaller than the largest picked card

I have an assignment for my algorithms module that requires us, amongst other things, to find the equations for the following question. Edit - Question Updated You have n cards with pairwise ...
0
votes
1answer
63 views

Probability randomly picked card is smaller than another picked card

Given a set of m cards that have values pairwise different with range 1 to m, what is the probability that after shuffling the card, and picking two of them, the first one is larger than the second ...
0
votes
0answers
47 views

Computing an estimator for a piecewise distribution?

Suppose I have a random variable $X$ that follows a distribution with a piecewise function $f(x|\theta)$. What is the correct way to compute an estimator $\theta$ for this function? Should the ...
3
votes
1answer
39 views

Find probability of a Poission 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 ...
1
vote
0answers
92 views

Randomized packing of items

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
0
votes
1answer
79 views

Frequency analysis/discrete uniform distribution in multiple choice tests

I may be using the wrong terms in the title but I read that if something is random then each character will occur an equal amounts of times. I read this when reading about the One-Time Pad cipher, ...
1
vote
0answers
19 views

Determinate State of Linear Congruential Generator from Results

I am curious on how someone would go about determining the state of a Linear Congruential Generator given its output. X(n-1) = (aX(n) + c) mod p Since the values ...
5
votes
0answers
166 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 ...
0
votes
0answers
24 views

Problem with an inequality from probability theory (Random matrix theory)

I read the following notes on random matrix theory http://www.umpa.ens-lyon.fr/~aguionne/cours.pdf . While reading Wigner's proof for the semi-cicular law I encoutered the following inequality on page ...
0
votes
2answers
81 views

Addition of probabilities and gambler's fallacy

Say you have a 1 in 6 chance of winning a card game. The more times you play, the higher the odds of you winning. $$P(\text{win over 1 trial}) = 1/6 \\ P(\text{win over 2 trials}) = 1/6 + 1/6 \\ ... ...
2
votes
1answer
64 views

Probability that number begins with one

I have three very similar algorithms generating very different results. In all of them I'm calculating distribution of first number of random number. First algorithm Here I'm generating random ...
0
votes
1answer
33 views

Generation of “random” multilinear polynomials for testing non-negativity algorithm

Multilinear polynomial is a multivariate polynomial where the exponent is zero or one. My instructor suggests to test my non-negativity algorithm with ...
1
vote
1answer
75 views

Plotting psuedorandom jagged parallel lines

I'm very interested in the morphogenic freehand drawings of John Franzen. I am looking to develop an algorithm which can draw lines such as these with some "entropy". That is, somewhat jagged or ...
1
vote
2answers
52 views

How to proof the randomness of a number sequence?

I've got a sequence of numbers generator by a "random number generator". Is there a way or a method to proof the randomness of the generator? How would I even compare randomness of generators? Or ...
0
votes
2answers
48 views

What is the statistical difference (if any) between these two methods of generating an n-digit random number?

To preface, this question is coming from a software developer so it's written from that perspective. If I need to generate a random number with $n$ digits, I could do it in one of two ways. a. Ask a ...
-1
votes
3answers
97 views

Fibonacci divisibility

Is $2051$ a factor of any fibonacci number? It is not a factor of any perfect number. The prime factors of $2051$ are $7$ and $293$, which are both prime. the $8$th fibonacci number, is the first ...
1
vote
0answers
18 views

Good notation for many random points approximating an area.

I'm trying to say that as the number of random coordinate points points you plot approaches infinity, it is equivalent to an area integral where each point is an infinitesimally small $\mathrm{d}x ...
0
votes
2answers
57 views

Exercise from probability

In normal deck of cards each of the cards have some rank (2 have rank 2, 3 have rank 3, ... , J have rank 11, Q have rank 12, K have rank 13 and A have rank 14). 3 cards are drawn. We have the random ...
1
vote
1answer
47 views

Generating Auto-Correlated Random Numbers with finite correlation length

How can I generate a lot of (for example N=20000 or more) auto-correlated random numbers {x_n, n=1,2,...,N} with uniform or normal probability distribution and finite correlation length (Here eq. ...
1
vote
1answer
37 views

How many iterations does it take to cover a range with random values?

Let's say I have a random number generator that generates integers uniformly from 0 to n-1 (where n is some positive integer). What is the expected number of iterations after which all the values ...
1
vote
0answers
37 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, ...
0
votes
1answer
39 views

Multiple independent random number streams

This question is somehow related to this one. Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in ...
2
votes
0answers
65 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. ...
1
vote
0answers
34 views

choose a list of words such that have equal letter frequency

I have a big list meaning full Words. surely letter frequency of this word list is different for each letter. Now my problem is to find a way to randomly select words from this word list to a new ...
1
vote
1answer
86 views

Generating a uniformly distributed set of numbers with negatives?

I have a number generator that can generate numbers between 0 and 1. I want to somehow use this generate a set of $N$ numbers that add up to $1$, and include negative numbers. These numbers must be ...
2
votes
1answer
50 views

Independent sequences

Let $\{x_i\}_{i = 1, ...,n}$ , $\{y_i\}_{i = 1, ...,n}$ be sequences generated by a pseudo-random number generator using different seed keys, for example $ x_0$ and $y_0$. Are $\{x_i\}$ and $\{y_i\}$ ...
1
vote
0answers
26 views

Reservoir sampling - understanding probabilites

I am reading about reservoir sampling(method for selecting random sample out of some data), but cannot understand a few things about probability I came across. The article at blog, says that if I'm ...
1
vote
1answer
31 views

linear dependncy of a random vector with respect to a reduced row echelon form in a finite field

Given a matrix with elements from a finite field $\mathbb{F}_q$, $A\in\mathbb{F}_q^{N\times M}$, where $q$ is the size of the field, $N<M$. Suppose that $A$ in the reduced row echelon form. ...
0
votes
0answers
32 views

Chaoticity and randomness in a time series

Suppose we have a time series : $X=\{X_t,t\in T\}$. How can we check if the data $X_t$ are random or they are the result of some chaotic behaviour of a nonlinear dynamical system? Is there some test ...
2
votes
0answers
68 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 ...
1
vote
4answers
108 views

What is an example for an algorithm which makes use the power of randomness?

Can someone give a (most simple) example for an algorithm on a machine, which has access to random numbers, and which is faster than any other known algorithm for the same task? My actual motivation ...
1
vote
2answers
76 views

Find the probability of two random real numbers $x$ and $y$ between $0$ and $2$, where $\min(x,y) < 2/3$

Here is a picture of what I did so far. http://sdrv.ms/HhxIvu I got a result of $\frac59$, because the total area is $4$, and I'm subtracting the square with side of $\frac43$. Can anyone confirm ...
0
votes
1answer
76 views

create random random whose sum is constant

Given N numbers. How can I decompose each element x in N into random values r1,r2,..rk (k can be a variable) such that the their sum is equal to x. What can we do if the rs are integers or irrationals ...
1
vote
1answer
95 views

Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
2
votes
0answers
136 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 ...
3
votes
1answer
263 views

Triangle Point Picking in 3D

To take random uniform points inside a triangle Triangle Point Picking method is used. But this is for 2D points, how can I take random points from a triangle that is defined by 3 arbitrary 3D points? ...
0
votes
1answer
48 views

Given a Sum, How to Randomly Generate Variables

I have five variables: A=2 B=3 C=4 D=5 E=6 I want to create a random array of these variables so that their sum equals a given number X. Example if X=21, a ...
2
votes
0answers
93 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 ...
1
vote
1answer
191 views

number of steps a random walk in a line on the nonnegative integers

let $T_n$ denote the number of steps a linear random walk on the nonnegative integers takes before reaching the position $n$ for the first time. What will be $\mathbb{E}[T_n]$. I tried to derive ...
0
votes
1answer
48 views

Prove that this is a legitimate PMF

I know that these are two properties of PMF. Non-negativity Sum over the support equals 1 However I can't show that this PMF's sum over the support equals 1.
0
votes
1answer
109 views

Construction of a random probability measure on the positive integers

Let $\mathcal{N} = \{1, 2, \ldots\}$ be the set of positive integers and let $\mathcal{F}$ be the $\sigma$-field of all subsets of $\mathcal{N}$. Let $X$ be a random variable taking values in ...
0
votes
3answers
115 views

How to discourage contestants from entering a lottery twice?

Suppose you have a lottery. And you want to prevent participants from buying multiple tickets. What would be the best way to discourage this? For example, increasing the win-chance for all previously ...
1
vote
1answer
62 views

probability of sequence of random variables

We're going to look at a random process, which is a sequence of random variables that depends on time. Let $X(t)$ = $A/t$ where A has the density $f_A(a)$ = $3/8$ $a^2$ for $ 0<=a <= 2$. Assume ...
1
vote
1answer
99 views

Is there a way to mathematically describe “surprise”?

Let's say that there are ten people entered into a random drawing, the winner gets some large prize. If I were one of those ten people, and I were to win, then I would be pleasantly surprised. If ...
1
vote
1answer
133 views

Finding the joint distribution of a random process with memory

I'm modeling a digital system as a random process and attempting to solve for the autocorrelation in order to arrive at the power spectral density of the process. The system is as follows: At any ...
1
vote
1answer
1k views

Probability density of Continuous uniform distribution over the unit circle

If we want to chose a point $(x,y)$ uniformly at random from a unit circle in a plane, why is the joint probability density of the random variable $f(x,y) = \frac{1}{\pi}$ for $x^2+y^2\leq1$? The ...
1
vote
0answers
46 views

Random Walk in confined region and loop configurations

Suppose I take a random walk on a 2 dimensional square lattice, but this lattice plane has a finite size, e.g. Dx*Dy. I can not cross the boundary, my step length is the lattice cell size, I either go ...
1
vote
1answer
269 views

problem on random variable in probability

A game consists of first rolling an ordinary 6-sided die once and then tossing a fair coin once. The score, which consist of adding the number of spots showing on the die to the number of heads ...
0
votes
1answer
39 views

Project on generating random numbers on GPU

I have been assigned a project on generating random numbers (specifically lognormal random numbers) on gpu. I have knowledge of probability and statistics and some programming experience but I do not ...