Questions tagged [algorithmic-randomness]

Use this tag for questions related to algorithmic randomness, which is the study of random individual elements in sample spaces.

74 questions
Filter by
Sorted by
Tagged with
78 views

Fixed-rate sampling without replacement

Suppose that we have a population of $N$ elements $E=\{e_1,e_2,...,e_N\}$, and a corresponding set of desired sampling probabilities $P=\{p_1,p_2,...,p_N\}$. Each element $e_i\in E$ should be sampled ...
36 views

Could my simple iterative algorithm for generating random numbers be favouring digits of value 0?

I have been creating a random number generator, using Python. My script starts by creating a one-dimensional $1 \times N$ matrix of integers ranging from 0 and 9. We can denote this matrix as $A$. I ...
44 views

An algorithm for enumerating subsequences of all infinite binary sequences?

We consider that an infinite binary sequence $s$ is not random in the sense of Martin-Löf. For all the $s$ sequences which respect this constraint, is it possible to build an algorithm which can ...
30 views

Question on random bits

Sample a uniformly random bit. Let $X$ be the corresponding random variable. Here is a randomized procedure to create two more output bits, denoted by random variables $Y_1$ and $Y_2$. To generate ...
73 views

Algorithm for sampling items fails the tests

I was looking into a coding exercise which asks the following: Given an array of positive integers $w$ where each $w_i$ describes the weight of the $i^{th}$ element, implement an algorithm that ...
43 views

Biased graph generating processes

Given a random process (algorithm) that is supposed to generate with equal probability graphs from a given class $\Gamma$. Assume the process is not obviously biased, i.e. generating graphs unevenly (...
46 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
29 views

What's the expected size of sampling for estimating percentile in a dataset?

Problem definition: D: a size n set of real numbers M: a size m set of real numbers sampled from D without replacement, each number in D has equal probability to appear in M. $m \leq n$ I want to ...
202 views

Are there any real-world applications for the logistic map (as defined in chaos theory)?

Is the logistic map only useful for theoretically exploring nonlinear dynamical systems, or can it be applied to real-world scenarios in any practical way?
42 views

Almost sure statements which don't hold for all Martin Löf random sequences

I have been looking into Martin-Löf random (MLR) sequences. The intuition is that when a statement $P$ is true for almost all sequences, it holds for ALL MLR sequences. For example, the strong law of ...
19 views

How big are periods in PCG?

I'm trying to figure out what is period of PCG generator XSL-RR-RR: https://www.pcg-random.org https://en.wikipedia.org/wiki/Permuted_congruential_generator If we use just a random multiplier and ...
33 views

Uniform sampling $k$ non-crossing $s$-$t$-paths in plane graph.

Let $G=(V, E)$ be a graph embedded in the plane and let $s, t\in V$ both lie on a common face. Shortest non-crossing $s$-$t$-paths $P$ and $P'$ are shortest paths (wrt. edge count) from $s$ to $t$ ...
277 views

Is compressibility a good test for randomness of a pseudorandom sequence?

I am interested in tests and definitions of randomness of a sequence generated by a pseudo-random number generator. A similar question was asked a few years ago, and the response was to use a ...
59 views

Is it possible to get the true generating function of a PRNG?

Since every sequence of pseudo-random numbers must be generated by deterministic means, it has to follow some underlying mathematical expression (function-like I guess). Suposse you intend to get this ...
56 views

Why does tSNE includes "Stochastic" on its name?

I know that in Machine Learning one classification of algorithms that researchers use is if they are deterministic or stochastic. I've been studying tSNE, but I don't get if "Stochastic" is ...
18 views

difference between sampling from different number system

Is there any difference in algorithm between sampling from different number system, e.g.sample from a standard Gaussian distribution $X \sim N(0,1)$ with samples defined on rational numbers $Q$ or ...
64 views

Understanding the Hiring assistant problem

I am reading Introduction to Algorithms by CLRS and saw the probabilistic analysis of the Hiring assistant problem Problem : $n$ people appear randomly for a job interview for an assistant . We hire ...
92 views

Proving Knuths Algorithm for generating a Poisson Distribution

I must prove that the following algorithm returns Poisson distributed numbers $k$. ...
52 views

A novice theory about lack of "randomness"

I have a theory, (have no idea even if this has been discussed before). In any set of numbers, you might find a pattern (given enough time), thus making it not random. Example: I was once given a set ...