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

36
questions

**1**

vote

**3**answers

127 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

72 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

132 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

149 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

89 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

64 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

187 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

137 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

69 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

66 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

100 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

381 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

106 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

253 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$ incomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example?
what is ...

**1**

vote

**0**answers

64 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

108 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

82 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

139 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

280 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

116 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

350 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

99 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

736 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

153 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

97 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

422 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

241 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

253 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

119 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

346 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

40 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

155 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

108 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

842 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

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

**8**

votes

**1**answer

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