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

33
questions

**4**

votes

**1**answer

174 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

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

**0**

votes

**0**answers

35 views

### Computational complexity of optimization algorithms using random algorithm theory

A fundamental and undoubtedly much-studied problem is that of determining not only whether or not an optimization algorithm converges to its optimum but also how fast it converges (see a discussion on ...

**0**

votes

**0**answers

32 views

### Is every productive set not Martin-Lof random？

every productive set is not Martin-Lof random，and so are some immune set.Therefore,do we have to have a definition for productive sets and such immune set which is different from Martin-Lof ...

**1**

vote

**1**answer

63 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

61 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

90 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**

votes

**1**answer

226 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

100 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

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

**0**

votes

**0**answers

24 views

### Reference request: generalizations of randomness for long sequences

I'm looking for information about generalizations of notions of randomness (Martin-Löf, etc.) for sequences of length $>\omega$. It's fairly easy to see where the natural choice points in coming up ...

**1**

vote

**0**answers

44 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

105 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

81 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

135 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

266 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

111 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

341 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

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

**7**

votes

**1**answer

583 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

150 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

413 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

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

**8**

votes

**0**answers

206 views

### Complete list of exceptions and efficient algorithm for Waring's problem

2 weeks ago, Samir Siksek http://arxiv.org/abs/1505.00647 proved more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, 303, ...

**2**

votes

**1**answer

107 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

323 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

39 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

146 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

106 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

788 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

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