0
votes
0answers
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 ...
1
vote
2answers
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: ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
4answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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)= ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
2
votes
3answers
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 ...
12
votes
3answers
907 views

Is there a possibility to choose fairly from three items when every choice can only have 2 options

Me and my wife are often not knowing which DVD to watch. If we have two options we have a simple solution, I put one DVD in one hand behind my back and the other DVD in the other hand. She will ...
8
votes
3answers
1k views

Will this procedure generate random points uniformly distributed within a given circle? Proof?

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