Questions tagged [algorithmic-randomness]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
1answer
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 (...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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?
2
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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$ ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
92 views

Proving Knuths Algorithm for generating a Poisson Distribution

I must prove that the following algorithm returns Poisson distributed numbers $k$. ...
0
votes
1answer
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 ...
1
vote
2answers
52 views

$\Sigma_{\tau \in S} 2^{-|\tau|} = 2^{-|\sigma|}$, for any prefix-free $S \subseteq 2^{<\omega}$ s.t. $[S] = [\sigma]$.

The Kolmogorov Inequality gives me $\Sigma_{\tau \in S} 2^{-|\tau|} \leq 2^{-|\sigma|}$, for any prefix-free $S$ extending $\sigma$. But equality seems to hold when $[S] = [\sigma]$. Notation: $[\...
1
vote
0answers
108 views

Performance - recurrence for the expected number of recursive calls

Here's what the following code is doing: The randomized algorithm selects the k-th smallest element in an unsorted array A[1...n], 1 < k < n. For simplicity of analysis it is assumed that all ...
1
vote
2answers
111 views

Formal statement of property of randomness of a sequence

Suppose we have a probability space $(\Omega,{\mathscr F},P)$ consisting of An arbitrary nonempty set $\Omega$ A collection ${\mathscr F}$ of subsets of $\Omega$ which is also a $\sigma$-algebra on ...
0
votes
0answers
45 views

Martin-Löf randomness tests relative to conditional probability?

Background: Martin-Löf's way of defining randomness of finite strings (over a finite alphabet such as $\{0,1\}$) and infinite sequences uses a generalized notion of a statistical test. Often, when ...
0
votes
1answer
92 views

Randomness Formal definition

What is the most accurate definition of randomness? I saw some posts concerning random variables, but I would say I don't intuitively think they present some kind of randomness, given that they have ...
1
vote
0answers
52 views

mathematical proof of fast convergence of an nature-inspired algorithm

I am using the Moth-flame optimization algorithm to solve a problem. The algorithm uses logarithmic spiral to update the position of the moths. I have been asked to provide a mathematical proof to ...
2
votes
1answer
99 views

Unexpected values returned by C++ noise generation functions

I'm porting the C++ libnoise library into another language. While doing so, I came across a function which appears to return inappropriate values, at least according to the original documentation from ...
0
votes
0answers
30 views

Why quasi-random sequences are generated in the interval [0,1]? Is it a normalized sequence generation?

The quasi-random sequences are generated using low discrepancy sequences and Koksma-Hlawka inequality explains the quasi sequence clearly. However, it is observed that these sequences are generated in ...
0
votes
0answers
191 views

boxing algorithm problem

This is a bit of a computational algorithm problem, I am not entirely sure if here would be the right place to ask this, but here is the problem. I got some “containers” that each can hold 15, and I ...
0
votes
1answer
40 views

Expectation in spectral sparsification algorithms

I am new to random matrices. I am studying the (Sampling) sparsification algorithms done by Daniel Spielman, Teng, Srivastava. They used the concept of graph sampling to obtain a good spectral ...
0
votes
0answers
14 views

Optimal Speed up of Las-Vegas Algorithm

As per my course requirement, I was reading a paper titled "Optimal Speed-up of Las Vegas Algorithm" by M. Luby et. al . I couldn't get around this Lemma $$T(S) = \sum\limits_{t \leq t_{1}} t \cdot ...
2
votes
2answers
77 views

How many bits of randomness needed to sample from $\operatorname{Bernoulli}(1/3)$

The title says it all. How can you take a sequence of random coin flops $x_1,x_2,\ldots,x_n\sim\operatorname{Bernoulli}(1/2)$ and generate a sample from a coin $X \sim \operatorname{Bernoulli}(1/3)$ ...
0
votes
1answer
99 views

Motivation for Algorithmic Randomness Definition

Wikipedia gives this definition for algorithmic randomness in terms of Kolmogorov complexity: "Given a natural number c and a sequence w, we say that w is c-incompressible if $K(w) \geq |w|-c$. An ...
1
vote
2answers
79 views

Shuffling an ordered list with a given degree of randomness

I feel like the following problem should have a well-known answer, but unfortunately I don't know the keywords to look up. I would like a procedure that takes as an input an ordered list of items, ...
2
votes
0answers
58 views

How to generate a uniform simple path from a rectangular grid graph?

I have an $m \times n$ grid graph. I want to generate a simple path from $(1,1)$ to $(m, n)$ uniformly from the set of all such paths. (Note I am not constrainted to move only right/down; the path ...
0
votes
1answer
67 views

If I roll 5 casino dice at the same time, does the order in which I read the results matter?

If I want to get a perfectly random sequence of numbers in range 1 to 6, possibly very long, and roll 5 casino dice at the same time, does the order in which I read the numbers from individual dice ...
1
vote
1answer
27 views

Does "for almost each object" make sense in this example?

In the 2nd paragraph at Kolmogorov complexity, these is the following sentence. "In particular, for almost each object it is not possible to compute even a lower bound for its Kolmogorov complexity .....
0
votes
0answers
67 views

Normal number and Kolmogorov complexity

For real number $r$, infinite sequence of its digits in base 10, (I mean 1/9=>1,1,1,1,1,1,1,1,1,1,1,1.....) I heard that if this sequence is the random sequence in the sense of kolmogorov complexity ...
-2
votes
1answer
33 views

Shuffling Cards by Grouping

Lets say I have 5 cards, a b c d and e. I group those as 2, 2 and 1, my first group contains a and b, second group contains c and d, and the last group contains only e. Then I mix those, by putting ...
-1
votes
1answer
90 views

What is polynomial-time random language?

What is polynomial-time random language? I have tried to found the definition by searching artilce, but failed. Any one give reference?
1
vote
2answers
91 views

How to make unlimited number of fair coin be equivalent to two fair dice that takes the sum of their outcomes?

I have an exercise in Randomized algorithm it takes me time to answer it but this king of question is new for me and I need a hint to begin with. Problem 1.3 [Motwani and Raghavan's textbook] (Due to ...
2
votes
2answers
194 views

Calculate mean value from given data

This question is about requesting some applicable algorithm rather than mathematical idea and is not part of any homework or study project. The solution may be obvious, but I can't see it by myself. ...
1
vote
0answers
69 views

Seeking general information about modal probability arithmetic

Imagine Peano Arithmetic extended with a modal operator $P_{n}^{\ge a/b}$, where $n$ is a variable possibly appearing free in the following expression and $a$ and $b$ are term symbols. Let $F_n$ ...
2
votes
1answer
140 views

The problem $K(x) \le K(y)$ is not decidable for Kolmogorov complexity $K$

Let $X$ be some finite alphabet. Given $(x,y) \in X^{\ast}\times X^{\ast}$, how to show that $K(x) \le K(y)$ is not decidable? I know that $K(x) \le k$ for some fixed $k$ is not decidable, so I tried ...
1
vote
0answers
133 views

Non-random movements

I know that the hedge fund Renaissance Technologies use computer-based models to predict price changes in financial instruments. These models are bases on analyzing as much data as can be gathered, ...
2
votes
1answer
3k views

Analysing a modification for Min-Cut Algorithm!

This exercise taken from the textbook "Randomized Algorithm" by Motwani and Raghavan. P.9, they give the following exercise to modify the min-cut algorithm: Exercise 1.2 Suppose that at each step ...
1
vote
0answers
60 views

Kolmogorov complexity measure of a formal system

Each formal system can be encoded in a binary string. For instance, you can use the input string that a pre-specified Turing machine needs in order to enumerate all the theorems in a theory in the ...
1
vote
1answer
764 views

Change in standard deviation when combining two sets of numbers

Say I have 2 Geiger counters that both generate a set of values (the counter measures background radiation). If I combine the two sets, how does the standard deviation of the new set compare to that ...
2
votes
1answer
139 views

"The digits used in artificial numbers are random while the real numbers aren't and their digits distribution is specific to their business"

Related to the question https://math.stackexchange.com/questions/1924178/tools-to-measure-the-nonrandomness-of-database, I'm somehow looking for some tools to measure the nonrandomness of databases. ...
3
votes
1answer
227 views

Are there strings with known Kolmogorov complexity?

I just looked into Kolmogorov complexity today and it appears to me that for a binary string of length $1$ (ex. '$0$') the Kolmogorov complexity must be $0$. It follows that Kolmogorov complexity ...
0
votes
2answers
406 views

Working with C++ for GF(2) [closed]

Pardon me if it is off topic.But, is there anyone who could suggest me some basics with how to get started with working with C++ for GF(2)?? I am new in C++.I am learning to working with arrays and ...