# 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.

40
questions

0
votes

0
answers

33
views

### Efficient generation of Gaussian processes with $\mathrm{Cov}(X_s, X_t) = t/s$?

let $X = (X_i)_{i\in \{1, \dotsc, n\}}$ be a Gaussian vector. If the covariance of $X$ assumes a shape like $$\mathrm{Cov}(X_i, X_j) = f(i-j)$$ for some function $f$, then $X$ is shift-invariant and ...

4
votes

1
answer

124
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-...

6
votes

1
answer

187
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 $\...

2
votes

0
answers

78
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 ...

1
vote

3
answers

178
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 &...

2
votes

2
answers

93
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 ...

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 ...

4
votes

1
answer

205
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 ...

3
votes

0
answers

107
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 ...

0
votes

1
answer

70
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 ...

4
votes

1
answer

204
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 ...

1
vote

0
answers

145
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
vote

1
answer

76
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 ...

0
votes

1
answer

73
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^\...

1
vote

0
answers

110
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?

4
votes

1
answer

574
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

116
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
votes

1
answer

284
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 ...

1
vote

0
answers

93
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
votes

0
answers

115
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 ...

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(...

1
vote

1
answer

151
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(...

4
votes

3
answers

330
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 ...

5
votes

0
answers

128
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 ...

4
votes

1
answer

375
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 ...

0
votes

1
answer

116
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 ...

8
votes

1
answer

1k
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 ...

2
votes

1
answer

171
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 ...

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 ...

3
votes

0
answers

465
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 ...

3
votes

0
answers

254
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 ...

9
votes

0
answers

269
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, ...

2
votes

1
answer

133
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 ...

2
votes

2
answers

398
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 \...

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
vote

0
answers

172
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}$, ...

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 ...

4
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 ...

3
votes

0
answers

119
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} ...

9
votes

1
answer

258
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 ...