# Questions tagged [algorithmic-randomness]

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

88 questions
Filter by
Sorted by
Tagged with
1 vote
38 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 ...
25 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 ...
48 views

### Finding a bound for an estimate of $\pi$ using a Monte-Carlo algorithm

I want to estimate $\pi$ using the following method let $Z$ be $0$ to start with repeated $N$ times: draw $u_1, u_2 \in [0, 1]$ and calculate whether or not $(u_1)^2 + (u_2)^2 < 1$, if so add $1$ ...
39 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",...
26 views

### Upper Bound to PoS of a congestion game with max λ players using a resource

Good morning everyone, I've been reasoning on this problem for severeal days, but I couldn't end up with a solution. Consider a congestion game for which we have the following guarantee: The cost ...
96 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 ...
11 views

### A question about integrality gap, approximation ratio

I am reading the paper on RPR2 rounding on approximation ratio of MaxCut problem. See this link. There is one sentence which is important to me but I don't understand its logic. I quote it here: If ...
61 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 ...
45 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 ...
81 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. ...
54 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. ...
56 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 ...
102 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 ...
87 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
60 views

1 vote
171 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 ...
1 vote
146 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 ...
105 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 ...
130 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 ...
1 vote
64 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 ...
109 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 ...
33 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 ...
262 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 ...
16 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 ...
172 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)$ ...
120 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
102 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, ...
70 views

### How to generate a uniform simple path from a rectangular grid graph?

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