Questions tagged [algorithmic-randomness]
Martin-Löf randomness and other randomness notions arising from computable tests; as well as related concepts such as Kolmogorov complexity, K-triviality, and effective Hausdorff dimension.
42 questions
0
votes
0
answers
25
views
Maximally "unexpected" binary time series
I'm sure this idea isn't new. Suppose a computer program has to predict
a binary time series by calculating the most probable continuation
(this is a widely known "joke" if you want to show ...
- 4,829
0
votes
0
answers
102
views
Formalizing the "pseudorandomness" of primes
Many conjectures about primes seem to revolve around the idea of "primes are random". So I thought about how this "randomness" may be formally defined, and came up with the ...
- 1
7
votes
0
answers
170
views
Nondeterminism in Magma software while computing generators of an elliptic curve
Computing generators of a Mordell curve
$$y^2 = x^3 - 44275089430000,$$
can be done in Magma by running the following code:
...
- 34.3k
4
votes
1
answer
142
views
Does the set of infinite random strings satisfy an analogue of immune sets?
Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-...
- 4,587
6
votes
1
answer
201
views
Reference request: generalized randomness
There is a plethora of notions of randomness for Cantor space ($\phantom{}^\omega 2$) (Schnorr randomness, Martin-Löf randomness, weak 2-randomness, the various forms of higher randomness such as $\...
- 1,155
2
votes
0
answers
79
views
Is identifying the best in randomly chosen $n$ elements, equivalent to identifying one from the best half of randomly chosen $2n$ elements?
Suppose we are given a set $U$, and a black-box objective function $f: U \mapsto [0, 1]$. The job is to maximise $f(\cdot)$. Now, for a given $\delta \in (0,1)$, consider the following randomised ...
- 221
1
vote
3
answers
269
views
Practical pseudorandom generators
It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem.
I am curious if someone developed kind of &...
- 791
2
votes
2
answers
99
views
Are finite subsets of bi-immune sets random?
Let $A$ be a bi-immune set, that is, an immune set whose complement is also immune. An immune set (let's say $A$) is a set of natural numbers (the natural numbers include 0) such that: i. $A$ is ...
- 6,132
0
votes
0
answers
136
views
Use $n$ different integers with $+$ or $-$ to make equations, find out the unused numbers
I am just a normal Chinese student and I can't communicate well with English. The question is there are $n$ different integers, we can use $+$ or $-$ to make equations to let the result be zero and in ...
- 11
4
votes
1
answer
262
views
Bi-Hölder embeddings of finite metric spaces
This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this ...
- 5,407
3
votes
0
answers
121
views
Applications of products of random matrices
I'm studying the paper "Matrix concentration for products" and I'm trying to find simple applications of the inequalities for the expected value of the spectral norm of products of random ...
- 183
0
votes
1
answer
73
views
Algorithm for economically sampling method for Gaussian matrix product
Let $A$ be an $n\times n$ random matrix with i.i.d. $N(0,\sigma)$ entries, for some $\sigma>0$ and let $x\in \mathbb{R}^n$. A direct computation shows that $Ax \sim N(0,\sigma x^{\top}x)$.
I would ...
- 5,407
4
votes
1
answer
206
views
Expectation of multiplied random variables given their individual expectations
Suppose that I have two non-negative real valued random variables $x, y \in Z_+$ that always satisfy $$x+y \leq 1.$$ Also suppose that $E[x] = 1/2$ and $E[y] = 1/4$. What is the maximum possible value ...
- 153
1
vote
0
answers
146
views
Algorithmic combinatorial discrete problem (randomized lazy update?)
We are given a vector $\mathbf{b}$ of size $h$. Initially we have $\mathbf{b}_i=1$ for all $i\in \{1, 2, \ldots, h\}$. In a sequential fashion, at each time step $t=1, \ldots, n$, an index $j(t)$ is (...
- 1,677
1
vote
1
answer
79
views
Non-relativized, Computable and Schnor randomness w.r.t a measure
Riemann and Slaman have some great work classifying what reals are 1-random with respect to a measure $\mu$ relative to $\mu$. In that paper they cite Levin and Kautz (but not to refs I can find) for ...
- 3,029
0
votes
1
answer
87
views
Kurtz randomness and supermartingales with infinite *limit*
Suppose you replace the usual success conditions for a supermartingale (lim sup is infinite) with the requirement that the actual limit is infinite, e.g. a supermartingale $B$ succeeds on $X \in 2^\...
- 3,029
1
vote
0
answers
127
views
Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level
Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?
- 3,084
4
votes
1
answer
672
views
Algorithm to generate free unlabelled trees uniformly at random
I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
0
votes
1
answer
118
views
Are all $P$-noncomputable sets $P$-random? [duplicate]
$P$ means polynomial complexity.
$S_p$ is class of all $P$_random sets, and $S_{pc}$ is class of all $P$ incomputable sets, is $S_{pc} \setminus S_p$ empty? If not empty, any example?
what is the ...
- 3,084
3
votes
1
answer
293
views
Relationship between P-noncomputable and P-random sets
$P$ means polynomial complexity.
$S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ noncomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example?
what is ...
- 3,084
1
vote
0
answers
111
views
Hutchinson-type algorithm for efficient computation of trace of inverse of non symmetric matrix
Let $A$ be an invertible $N$-by-$N$ matrix, for some large $N$ (say $N = 10^6$). Suppose the only thing we know how to do is apply $A$ to a vector, i.e compute matrix-vector products $Az$.
Question....
- 6,853
6
votes
0
answers
116
views
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate $P=BPP$ in $1986$. They do this without getting into circuit lower bounds and from a different view ...
- 13.9k
0
votes
0
answers
84
views
Deterministically finding a subsequence of integers matching modular roots?
Take two integers $n$ and $m$ with $0<\log_2m<n<m$ and let $r_1=f_1(n)\bmod m$ and $r_2=f_2(n)\bmod m$ for functions $f_1,f_2:\mathbb Z\rightarrow\mathbb Z$.
Denote the $\ell$ roots of $(f_i(...
- 13.9k
1
vote
1
answer
154
views
Find probability of non-stationary inputs into Turing machine?
Consider some finite string $x=(x_1,x_2,...,x_{n-1},x_n)$ that is drawn from a non-stationary process. Would it be possible to use the algorithmic probability formula, defined by Solomonoff as,
$$
P_M(...
- 91
4
votes
3
answers
363
views
Example of concrete statement which requires probabilistic algorithm
In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...
- 781
5
votes
0
answers
132
views
Subsequence of a sequence of digits of an algebraic irrational number
Consider an algebraic irrational number in $(0,1)$ with binary expansion
$x = \sum_{n\ge 1} \frac{a_n}{2^n}$. Is it possible that the number $\sum_{n\ge 1}\frac{a_{2n}}{2^n}$ is again algebraic ...
- 715
4
votes
1
answer
386
views
Existence of normal number except random numbers
For normality, see https://en.wikipedia.org/wiki/Normal_number. For random number/sequence, see https://en.wikipedia.org/wiki/Algorithmically_random_sequence.
Now, is there any number that is normal ...
- 3,084
0
votes
1
answer
136
views
Randomness defined in Kolmogorov complexity is identified with one in probability theory/stochastic process?
Actually, in many works of probability theory/stochastic process, there is no explicit definition of randomness. Maybe because we think we can deduce the definition easily.
But in Kolmogorov ...
- 3,084
8
votes
1
answer
2k
views
What is the precise relation between Kolmogorov complexity and Shannon's entropy?
Consider the discrete case:
Shannon's entropy is $H(x)=-\sum\limits_i^n p(x_i) log\space p(x_i)$.
Probability based on prefix-free Kolmogorov complexity is $R(x_i)=2^{-K(x_i)}$ where $K(x_i)$ is ...
- 3,084
2
votes
1
answer
173
views
Generating an arbitrarily long sequence with decreasing Kolmogorov complexity of terms
Is there an algorithm which, given a string $s$, generates a sequence of $|s|$ strings, such that it can be proven in some axiomatic system $S$, that the Kolmogorov complexity of each successive ...
- 851
2
votes
0
answers
100
views
Non-uniform distribution in digits of chaotic orbits?
For a class I was teaching, I was demonstrating time-series analysis with the famous discrete-time dynamical system $x_{n+1} = ax_n(1-x_n)$, where $a = 4 - \epsilon$ ($\epsilon$ ``small'') and ...
- 413
3
votes
0
answers
479
views
A question about the Chaitin constant of a theory
Chaitin's famous incompleteness theorem states that for every r.e. theory $T\supseteq Q$ in the language of arithmetic, there is a constant $d_T$ such that for any $m\geq d_T$ and any $x$, $T$ can ...
- 870
3
votes
0
answers
263
views
"Kolmogorov complexity" of models of computation
This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...
- 3,612
9
votes
0
answers
275
views
Complete list of exceptions and efficient algorithm for Waring's problem
2 weeks ago, Samir Siksek https://arxiv.org/abs/1505.00647 proved the more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, ...
- 91
2
votes
1
answer
144
views
Largeness, generic, random points
As presented in Oxtoby's book ( http://link.springer.com/book/10.1007%2F978-1-4615-9964-7 ), there are two notions of largeness for subspace $Y$ of a given space $X$:
Topology: $X$ is a topological ...
- 370
2
votes
2
answers
428
views
Absolutely algorithmically random infinite sequence
Let's call an infinite sequence of bits $f:N\rightarrow \{0,1\}$ absolutely random if any computably constructed subsequence is not computable, i.e. there aren't monotonic computable function $g:N \...
- 1,318
2
votes
0
answers
44
views
largest size for a randomness extractor
I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
- 1,109
2
votes
0
answers
179
views
Kolmogorov complexity proof of Lovasz local lemma
Roughly speaking, the Kolmogorov Complexity proof of Lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, ...
- 69
3
votes
1
answer
116
views
Disobedience of some complete r.e. set to some additive cost function
An additive cost function is defined as $c: \omega\times \omega \to \mathbb{Q}_2$ such that it is recursive, monotonic (i.e. $c(x+1,y)\leq c(x,y)\leq c(x,y+1)$ and $c(x,y)=0$ whenever $x\geq y$, the ...
- 3,038
5
votes
3
answers
1k
views
Is There An Algorithmic Complexity Of A Random Distribution
Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
4
votes
0
answers
122
views
Weak randomness relative to finite-state machines
Is there a nice example of a sequence that looks random to any predictor whose predictions use a finite-state machine?
More precisely, consider a finite-state machine $M$ with input alphabet {0,1} ...
- 19.7k
9
votes
1
answer
266
views
Cohesive set with degree below non-high Martin-Löf random reals
A set A is cohesive if $A\subseteq ^* W_e$ or $A\subseteq^* \bar{W_e}$ for each $e\in \omega$ (standard enumeration of r.e. sets). By Jockusch and Stephan's 1993 paper 'A cohesive set which is not ...
- 3,038