0
votes
0answers
30 views

Can someone help me with the following math question/dilemma?

I have a pool of objects that are randomly selected from a global object database. The objects certain numeric attributes: The objects from the pool are fed to users in real time Users will either ...
2
votes
1answer
23 views

The probability of getting a certain image by random pixelation

Well, seeing that I'm terribly bad at math I don't know how to solve this, I'll try to explain, excuse me if I sound dumb. Just suppose that I've got a photo/image with 320x240 resolution and 24 bit ...
0
votes
1answer
44 views

Need to figure out how to do the math for deck of cards using different searches.

Below are the two questions I found from the websites ( I have added the link below ), that I am interested in learning the answers. My intention are not to post the answers for that guy but, I ...
-1
votes
1answer
44 views

Probability of 1 at both end of string

Given a string S having N characters long and consists of only 1s and 0s. Now given an integer K, let us pick two indexes i and j at random between 1 and N, both inclusive. What's the probability ...
0
votes
0answers
51 views

Probability with dice sum K

Alice rolls a N faced die M times. she adds all the numbers she gets on all throws. What is the probability that she has a sum of K. A N faced die has all numbers from 1 to N written on it and each ...
0
votes
4answers
38 views

Generate random numbers in a random fashion

How can I generate 9 random numbers between 1 to 9,without repetition, one after another. Its like: Lets assume that the first random number generated is 4, then the next random number has to be in ...
0
votes
1answer
39 views

Prove that $\sum_{i=0}^\infty i p_i = \sum_{i=1}^\infty q_i$

Given a table with m slots, indexed $0,1,\dots, m-1$ and n keys that are included in this table, $n \lt m$, with $m-n$ slots being empty, I'm given an algorithm that given a certain permutation of the ...
2
votes
0answers
16 views

map if-then-else to probability [closed]

I need an algorithm to transform game rules (p&p role playing) to probabilities, specifically conditional constructs built from if-then-else with conditions made of the boolean and relational ...
2
votes
0answers
52 views

“Alice and Bob” problem with matrices

Alice has a binary matrix $A$, and Bob has a binary matrix $B$. Both matrices are of size $n \times n$. Alice and Bob want to check if the matrices are equal except for exactly $1$ entry. Alice has to ...
0
votes
2answers
357 views

Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
1
vote
0answers
20 views

Choosing between increasing sample size and testing for failures

I have a large set of data that shows things (let's call them cars) have performed over the years against various different tests (say, crash test, braking, gas mileage, etc.). What I'm doing is ...
0
votes
0answers
63 views

What's the probability that Tom's bag will weigh more than Sally's?

Assume all cantelopes take on an integer weight in ounces from 0 (an extremely light apple) to 1000 inclusive. Tom has 50 cantelopes of weights $\{T_i: 1\leq i\leq 50\}$. Sally also has 50 ...
13
votes
4answers
185 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 ...
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
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 ...
3
votes
1answer
92 views

Expected Value of this function

Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where ...
1
vote
0answers
18 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
0
votes
1answer
78 views

Generating Random Serialnumber with least similarity

I want to generate 16-digits hexadecimal serial-number like: F204-8BE2-17A2-CFF3. (This pattern give me 16^16 distinct serial-number But I don't need all of them as I describe below) I need an idea ...
0
votes
0answers
19 views

Efficient algorithm for point estimation of a dependent random variable

Suppose $X$ is a normal-distributed random variable and $f$ is a known smooth function (possibly quite complicated, with many oscillations). Let $p(y)$ be the pdf of the dependent random variable $Y = ...
0
votes
1answer
26 views

Conditional probability algorithm problem

Byteasar has just arrived at the Bytetown airport and is waiting for his luggage. There are n people (including Byteasar) who were traveling this plane and each of them is waiting for exactly ...
0
votes
0answers
33 views

Why is Expectation Maximization algorithm guaranteed to converge to minimum, even local?

I have read a couple of explanations of EM algorithm (e.g. from Bishop's Pattern Recognition and Machine Learning and from Roger and Gerolami First Course on Machine Learning). The derivation of EM is ...
0
votes
0answers
20 views

Find error in a stochastic algorithm

I have $n$ cities, and I want to simulate the transition of people between these cities according to some rules (not all the cities are connected). Each city have $m_n(t)$ citizens and a rate $r_n(t)$ ...
0
votes
0answers
45 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 ...
6
votes
2answers
193 views

Average complexity of random-pick comparison sort

Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures ...
1
vote
0answers
48 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
0
votes
1answer
53 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
0
votes
0answers
52 views

GA (Genetic Algorithm) and stochastic simulation to solve optimization in R

My problem is to solve the following optimisation problem using GA (Genetic Algorithm)and stochastic simulation. The goal is to solve the maximisation problem : \begin{equation*} \begin{aligned} ...
7
votes
3answers
257 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
5
votes
2answers
95 views

Puzzle about voting

I came across about this puzzle which I'm not sure how to go about. Suppose there are $L$ leaders and $F$ followers, with $1 < L<<F$. A leader makes a binary decision, $0$ or $1$ with same ...
0
votes
0answers
39 views

Probability, linear independence and study of variant of Lights Out

Using Arduino, some leds and pushbuttons I've created a simple variant of the mathematically popular game "Lights Out". In my variant, the starting configuration is always all lights on; what changes ...
3
votes
0answers
40 views

Random convex shapes containing a ball

I'm interested in the properties of randomly generated convex shapes in $n$-dimensional space. Suppose I were to generate $v$ uniformly distributed random points on the $n$-ball of radius $R$. What ...
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 ...
3
votes
1answer
917 views

What is the expected number of swaps performed by Bubblesort?

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no ...
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 ...
2
votes
2answers
117 views

How to pick a random node from a tree?

How can I pick a random node from a tree, given the following constraints? We are given the root of the tree, and at every node we are given its children nodes. But we do not know what its children ...
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
60 views

Fast way to estimate cardinal number of subset

I have a large set $S$ of items, but the set is not exactly known. All I know are the cardinal numbers of categories i.e. a number of disjoint subsets, $ \vert{S_1}\vert \dots \vert S_n\vert$ with ...
-1
votes
1answer
63 views

How to compute conditional expectation of a log function

I've been studying the Expectation Maximization algorithm. According to the formula shown here, what I have to do in the M step is to compute a new $\theta$ that maximizes the conditional expectation ...
0
votes
1answer
186 views

PageRank algorithm. Iterative approach.

Given we have 4 nodes: A, B, C, D. A -> B and A <- B, B -> C, C -> D, C -> A and C <- A, D->A. We know only the starting probability of C which is 1. If we start from node C, what are the ...
1
vote
3answers
847 views

gradient descent optimal step size

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
0
votes
1answer
132 views

Using Chernoff bound to analysis the Lazyselect algorithm

It's my homework of the course of randomized algorithm. In the textbook (Randomized Altorithm by Rajeev Motwani et.al.), the author analyzed this algorithm using Chebyshev bound, but are there any ...
2
votes
1answer
159 views

Quicksort analysis problem

This is a problem from a probability textbook, not a CS one, if you are curious. Since I'm too lazy to retype the $\LaTeX$ I will post an ugly stitched screenshot: This seems ridiculously hard to ...
0
votes
1answer
48 views

Probability of getting distinct numbers out of two differently distributed variables.

Assume you have $X$ and $Y$. They both take the same values, but they have different distributions, for example: $X$, $Y$ can be: $\{1,2,3\}$ $X$ has probabilities: $\{\frac{2}{7}$ ...
2
votes
1answer
111 views

Bounding the power of expected value of functions of a random variable.

I am interested in a problem and I do not know where to start looking for possible similar setting. If anyone has a direction to suggest, it would be greatly appreciated. Consider a (finite) set ...
0
votes
1answer
314 views

How can I calculate the exact expected value of merge sort comparison (not O(n))?

First, the question stated that I have one unsorted list and then I have to split it out into two lists by fair coin flips. (Ex. Head goes A-list, tail goes B-list) Second, I'm trying to solve the ...
2
votes
4answers
287 views

Can you simulate any probability with biased coin throws?

What you're given: $p \in (0,1)$, but you don't know the value of $p$. You have an algorithm $\mathcal{A}_p$ that returns $1$ with a probability of $p$ and $0$ with a probability of $(1-p)$. You ...
5
votes
2answers
135 views

Choosing between $n$ things using dice?

For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die? For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, ...
0
votes
1answer
42 views

Probability : Dividing a list into 2 classes

I have a list of integer numbers ($n$). I am dividing it into two parts $n_1$ (smaller) and $n_2$ (bigger) such that the length of $n_1 \ge a*n$; $a$ is positive and $a \lt 0.5$. What is the ...
1
vote
0answers
73 views

Maximum Independent Set on Path and Ring

I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...