# Questions tagged [algorithmic-randomness]

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

90 questions
Filter by
Sorted by
Tagged with
23 views

1 vote
43 views

### Probability for a randomly generated string to have the same suffix as the prefix

I am working with randomly generated strings and the minimum fractional period of those string. The minimum fractional period of a string $s$ can be found by checking the eqaulity between the suffix ...
42 views

### Testing of randomness of binary bit sequences

I am trying to test randomness of binary bit sequence using NIST test suite. The tests applied for testing requires longer length of bit sequence. I have 256 bits sequence. Is it a good approach to ...
40 views

### Do all Turing-complete systems converge on a single universal function w.r.t. description redundancy?

Let $L$ be any Turing-complete language. Let $d_L(n)$ be the number of distinct algorithms expressible in $L$ using at most $n$ bits. I'm not sure how to properly define "distinct algorithm",...
• 6,004
289 views

### Kolmogorov Complexity and Compression Schemes

My question concerns strings with low Kolmogorov Complexities and if there is a single compression scheme that can be used to compress them I have been introduced to Kolmogorov Complexity through ...
• 256
81 views

### Randomly splitting a group into two equal teams using only a fair coin

A few days ago a group of 8 of us had to split into two teams of 4 for the purposes of competing in a trivia night. Notwithstanding that it was far from optimal as a trivia-winning strategy, we ...
• 4,282
90 views

### Do random number generators use prime numbers because the gaps between them are random?

Many random number generators like Linear Congruential Generator and the Marsenne Twister generator use prime numbers. Is it to capitalize on the fact that the gaps between the primes are thought of ...
• 195
87 views

### Dividing distinguishable cards into distinguishable hands where some hands cannot contain some cards

I am making a computer program to play cards, for this algorithm to work I need to deal cards out randomly. However, I know that some people cannot have some cards due to the rules of the card game. ...
• 2,180
64 views

### Balls and bins lower bound with random algorithm

Assume we have $n$ bins and $B \sim Binom(nk,p)$ balls to distribute in an equitable. Furthermore, assume that each ball arrives one at a time and must be placed in a bin before the next arrives. ...
• 119
71 views

### How to combine two Monte Carlo algorithms into a Las Vegas one?

Consider a decision problem $D$ with corresponding Monte Carlo algorithms $X$ and $Y$ satisfying the following properties: If $D(s)$ is true, then $X$ returns true with probability $p$ and false ...
• 21
147 views

### How to distribute $N$ items into $M$ groups the "most" random way?

There are $N$ "items" $s_1, s_2, ..., s_N$ and $M$ "buckets" with capacities $c_1, c_2, ..., c_M$ such that $\sum_{j=1}^{M}c_j = N$. In a document I'm reading (some industry ...
• 161
90 views

### Does a number n raised to itself (n^n) will have digits depending on the original number n? [closed]

Consider, 7^7 = 823543, the digit 3 in 823543 is repeated two times, is it possible that a number raised to itself can have a higher repetitions of any other digit or is it random. Now consider, 93^93 ...
1 vote
73 views

• 51
1 vote
196 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 ...
• 43
1 vote
170 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 ...
• 160
141 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 ...
• 1,338
163 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 ...
• 121
82 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 ...
113 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 ...
41 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 ...
283 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 ...
54 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 ...
• 439
18 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 ...
250 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)$ ...
• 1,156
133 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
120 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, ...
• 9,666
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 ...