# Tagged Questions

27 views

### Slot size bound for chaining

This is a question from CLRS Q) Suppose that we have a hash table with n slots, with collisions resolved by chain-ing, and suppose that $n$ keys are inserted into the table. Each key is equally ...
30 views

### Randomized Algorithm

I asked this question earlier but I wanted to change the problem. A band has tour sites A, B, and C. They get paid every time they play at each tour site, specifically: ...
60 views

### Probability Analysis of a Randomized Algorithm

A rock band has three sites A, B, and C that it needs to perform at. The band performs at site A, then randomly chooses between B and C as to where it performs next. The band keeps choosing one of the ...
24 views

### Computing standard errors using EM algorithm

I'm applying the EM algorithm to a hidden markov chain (the $\mathbf{Z}=\{Z_1,...,Z_n\}$ variable), with observations(the $\mathbf{Y}=\{Y_0,...,Y_n\}$ variable) dependent not only on the hidden markov ...
44 views

### Probablity of producing a finer balance in quicksort

So this question is a starred one in CLRS Q) Argue that for any constant 0< $\alpha$ $\leq$1/2, the probability is approximately 1-2$\alpha$˛that on a random input array, PARTITION produces a ...
108 views

### What is an example for an algorithm which makes use the power of randomness?

Can someone give a (most simple) example for an algorithm on a machine, which has access to random numbers, and which is faster than any other known algorithm for the same task? My actual motivation ...
40 views

### Array sort input

Suppose that there is an algorithm which sort a sequence of $n$ elements $$a_1, a_2, ..., a_n$$ Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. Is it ...
131 views

### probability of sum of a given set of whole numbers being greater than a certain number

There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a ...
41 views

### Interpretation of “expected cost” of an algorithm

I'm studying randomized algorithms and I sometimes come across results like (1) The algorithm has an expected $O(f(n))$ cost. and (2) With constant probability, the cost is bounded by ...
139 views

### Require help in writing the algorithm for my cricket simulation game

I am trying to write the algorithm for a cricket simulation game which generates runs on each ball between 0 to 6. The run rate or runs generated changes when these factors come into play like Skill ...
101 views

### How to vary lambda in exponentially distributed numbers

I am implementing an exponentially distributed random number generator (RNG) based on George Marsaglia's Ziggurat algorithm. I previously used the algorithm to create a normally distributed RNG. By ...
47 views

### Computationally efficient means of determining distance in the Skorohod Topology?

I have two functions f and g in a computer. Domain 1...N. I'd like to compute their distance using the Skorohod Topology in an efficient manner. (I first ran across this metric many years ago in ...
116 views

### Is there another solution for write the algorithm by matlab?

I have an algorithm as you can see below and i wrote it with different 2 ways but it seems there are problems for both solutions.is there any alternative to write it with different way? X_i(k+1)= ...
158 views

### N piles of hidden cards of known marginal probability distribution, then a card is revealed in one of the piles.

I am currently trying to use probability theory to help solve a programming problem involving Monte Carlo Tree Search with Information Sets and have hit a roadblock. The problem can be described as ...
2k views

### Intuition behind the concept of indicator random variables.

I am studying Randomized Algorithms chapter in the book "Introduction to Algorithms" by Cormen et al. In this chapter the book introduces the concept of an indicator random variable and state that ...
767 views

### How to transform normally distributed random sequence N(0,1) to uniformly distributed U(0,1)?

Everybody knows how to convert U(0,1) to N(0,1). However does anybody know an efficient algorithm solving the opposite task? I mean how to generate U(0,1) sequence from N(0,1) one? Asking because a ...
48 views

### random Algorithm over Random input-help needed

A random Algorithm $A$ receives input in $[n]$ it's know that when the probability is taken over input that was chosen randomly over uni-formal distribution over the algorithm randomness the ...
89 views

### Existence of a general-purpose (almost) universal optimization strategy

From Wikipedia about interpretations of no free lunch theorem A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization ...
97 views

### What is the maximum value of the minimum number of balls per bin?

$S$ people, $N$ bins, each person has a given subset of bins he can cover, each person is given $t$ balls. Question: What is the maximum value of the minimum number of balls per bin? i.e., allocate ...
61 views

### Is there a way to find $P(H_h)$, $P(E_\epsilon|H_\eta) (1 \leq \epsilon \leq e)$ and $P(E_\epsilon) (1 \leq \epsilon \leq e)$?

The problem: If we have $P(H_\eta|E_1,E_2,...,E_e)(1 \leq \eta \leq \mathbb{H})$ and $P(E_1,E_2,...,E_e)$ for all True and False values of $E_\epsilon(1 \leq \epsilon \leq e)$ and ...
140 views

### Distribution of a random variable related to insertion sort

I am given a uniformly chosen permutation of the set $\{1,\ldots,n\}$ as an array $A[1,\ldots,n]$. For an integer $1 \leq j \leq n$ I am studing the distribution of the variable $X$ counting the ...
180 views

### How can I generate a random DFA with uniform distribution?

I need to generate a Deterministic Finite Automata (DFA), selected from all possible DFAs that satisfy the properties below. The DFA must be selected with uniform distribution. The DFA must have ...
214 views

### Expected time of tree search algorithm on random input

We have a perfect binary tree on 2^k-1 nodes. Every node in the tree is marked with probability 1/2, and a node is either marked or unmarked. We want to find a marked node and return it. Our algorithm ...
Consider the task of generating random points uniformly distributed within a circle of a given radius $r$ that is centered at the origin. Assume that we are given a random number generator $R$ that ...