## Probability of reaching a state in asymmetric random walk

Consider the following random walk:

Namely, if $$S_i$$ is the state at time $$i$$, then $$Pr(S_{i+1}=1|S_i=0)=1$$, and for every $$s>0$$ we have
$$S_{i+1}|S_i=s= begin{cases} s+1 & text{w.p. }1-p\ s-1 & text{w.p. }p end{cases}.$$
In my application, $$p>frac{1}{2}$$. I’m interested in two quantities, $$Pr(S_T > H)$$ and $$mathbb E(S_T)$$. My intuition is that $$Pr(S_T > C ln T)leq frac{1}{T^2}$$ for some global constant $$C$$, and that $$mathbb E(S_T)=o(1)$$. However, I couldn’t show it (yet).

Any ideas?

Here are some trivial claims. First, $$Pr(S_T > H) leq exp(-frac{H^2}{T})$$ due to Azuma’s inequality, but that doesn’t use the value $$p$$ nor the fact that $$p> frac{1}{2}$$. Second, $$mathbb E(S_T) leq O(sqrt{T})$$ since $$S_t$$ is stochastically dominated by a symmetric random walk, for which the expected place at time $$T$$ is $$O(sqrt{T})$$.

The stationary distribution is easy to find, being $$pi_0=1-frac{1}{2p}$$ and $$pi_i = frac{pi_0}{p} left(frac{1-p}{p}right)^{i-1}$$, but I’m not sure how to use it.

## random walk – Expected number of stepds to reach 1 from n

Suppose a particle is moving in discrete steps. When it is at position $$nge1$$, it takes a step of size $$X_n$$, and moves to $$n-X_n$$, where $$X_n$$ is a random variable taking values in $${iinBbb{Z}mid ile n-1}$$. Suppose there is a non-decreasing function $$g:Bbb{R}^+toBbb{R}^+$$ (where $$Bbb{R}^+$$ is the set of positive reals). All that we know about the distribution of $$X_n$$, is that $$Bbb{E}(X_n)le g(n)$$.

Let $$T_n$$ be the number of steps the particle takes to reach $$1$$ (for the first time). How can I calculate $$Bbb{E}(T_n)$$ in terms of $$g(n)$$?

I have solved the problem for a much simpler case, where $$X_n$$ could only take the values $$1,2,cdots,n-1$$. This simpler version can be easily solved via induction, and it turns out
$$Bbb{E}(T_n)leint_1^nfrac{dx}{g(x)}$$

How do I solve it for the more general case? Thanks in advance.

## unity – Parameter ‘Walk’ doesn’t exist?

I’m trying to make walk animation. But when I try to change animation idle to walk, ıt doesn’t work.
It says ‘Parameter “Walk” doesn’t exist’but I added parameter and script works. I can manually change parameter and it works(walk animation is playing). But when I try to change via script, ıt doesn’t work.

Here are codes

``````public class Controller : MonoBehaviour

private Rigidbody rb;

private float xPos;

Vector3 playerMovement;

(SerializeField) Animator anim;

private void Awake() => rb = GetComponent<Rigidbody>();

private void Start()
{
xPos = transform.position.x;
}

// Update is called once per frame
void Update()
{
Move();
}

private void Move()
{
float mH = Input.GetAxis("Horizontal");
playerMovement = new Vector3(0, 0, mH);
anim.SetFloat("Walk", 1);
transform.position = new Vector3(xPos, transform.position.y, transform.position.z);
}
``````

## c – Random walk on a grid

``````// generate a random "walk" of letters from A to Z in a 2D grid, assuming a
// character set with contiguous values of uppercase letters (e.g. ASCII);
// stops if the "walker" gets stuck
// example of a successful walk:

//  A  .  .  .  I  J  K  .  .  .
//  B  C  F  G  H  .  L  .  .  .
//  .  D  E  .  .  .  M  .  .  .
//  .  .  .  .  .  O  N  .  .  .
//  .  .  .  .  .  P  .  .  .  .
//  .  .  .  .  .  Q  .  .  .  .
//  .  .  .  .  .  R  S  .  .  .
//  .  .  .  .  .  .  T  U  .  .
//  .  .  .  .  .  .  .  V  W  Z
//  .  .  .  .  .  .  .  .  X  Y

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <ctype.h>

#define GRID_SIZE 10

// movement directions
#define DIR_NUM 4

#define UP      0
#define LEFT    1
#define DOWN    2
#define RIGHT   3
#define ANY     (-1)

bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
char grid(rows)(cols));
void generate_random_walk(size_t rows, size_t cols, char grid(rows)(cols));
void print_array(size_t rows, size_t cols, char grid(rows)(cols));

int main(void)
{
char grid(GRID_SIZE)(GRID_SIZE) = { 0 };

generate_random_walk(GRID_SIZE, GRID_SIZE, grid);
print_array(GRID_SIZE, GRID_SIZE, grid);

return 0;
}

void print_array(size_t rows, size_t cols, char grid(rows)(cols))
{
for (size_t r = 0; r < rows; ++r) {
for (size_t c = 0; c < cols; ++c) {
char grid_c = grid(r)(c);
printf(" %c ", isalpha(grid_c) ? grid_c : '.');
}
putchar('n');
}
}

// checks all the directions by default (ANY)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
char grid(rows)(cols))
{
bool cangoup    = (rpos > 0) && grid(rpos - 1)(cpos) == 0;
bool cangoleft  = (cpos > 0) && grid(rpos)(cpos - 1) == 0;
bool cangodown  = (rpos < rows - 1) && grid(rpos + 1)(cpos)  == 0;
bool cangoright = (cpos < cols - 1) && grid(rpos)(cpos + 1)  == 0;

switch (dir) {
case UP:    return cangoup;
case LEFT:  return cangoleft;
case DOWN:  return cangodown;
case RIGHT: return cangoright;
default:    return cangoup || cangoleft || cangodown || cangoright; // ANY
}
}

void generate_random_walk(size_t rows, size_t cols, char grid(rows)(cols))
{
size_t rpos, cpos;

srand((unsigned int) time(NULL));

rpos = cpos = 0;
grid(0)(0) = 'A';
for (char c = 'B'; c <= 'Z' && can_move(ANY, rpos, cpos, rows, cols, grid); c++) {
// move in a random direction
for (int dir;;) {
dir = rand() % DIR_NUM;
if (can_move(dir, rpos, cpos, rows, cols, grid)) {
switch (dir) {
case UP:    --rpos; break;
case LEFT:  --cpos; break;
case DOWN:  ++rpos; break;
case RIGHT: ++cpos; break;
default:
printf("Impossible movement direction.n");
exit(EXIT_FAILURE);
}
break; // break out of the loop
}
}

// leave a trail
grid(rpos)(cpos) = c;
}
}
``````

To summarize, this program prints a grid with a random walk of uppercase letters in order. If the “walker” cannot move in any direction due to lack of space around it (up, down, left, and right), the walking terminates.

What I’m interested in, aside from general tips regarding my code that you may be able to give me, are two things:

1. I’ve read that functions shouldn’t normally take more than 2–3 parameters; do you think my functions really “suffer” from taking more than 3 parameters, and if so, how would I go about mitigating that?

2. Should I be using a `size_t` when looping over an array or similar, or should I use an `int` instead? I’ve read here on Stack Exchange various opinions concerning this: some people say `size_t` should always be used since it’s essentially undefined behavior if the array’s size is greater than `MAX_INT`, etc., while others say unsigned and signed types ought not to be mixed (and I generally have to use them in expressions that undergo the usual arithmetic conversions), and this is a major source of bugs. Pragmatically, I believe I should therefore use a regular `int`. There’s another thing I’ve noticed, and that is if I have to actually use these counters to perform some calculation: in those cases I really have no recourse, and what I end up doing is simply casting and praying, hoping that the array is of a reasonable size (i.e. that my `size_t` counter, or the result of the expression isn’t out of the representable range for an `int`). I think this is even worse than using an `int` from the beginning, since the interface that the `size_t` type provides is not conformed to, so my code is “lying” to both itself and the reader.

Note that I would use an `enum` instead of the `#define` definitions for the directions, but my book hasn’t gotten to them yet, so I think we shouldn’t focus on this. Also, I’ve looked at other questions with this same exercise, but the code/approach presented there is somewhat different.

## Given graph G and vertices v and w can you non-deterministically walk the “least Hamiltonian path” from v to w, if it exists?

My understanding of non-deterministic algorithms is that they’re “as lucky as you want”.

…you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices `v` and `w`, if there’s a `vw` path, then you can non-deterministically walk a `vw` path, luckily correctly guessing the vertices to walk in a `vw` path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I’m not sure.

Therefore, my first question is: if you can non-deterministically walk a `vw` path, can you non-deterministically walk a Hamiltonian path from `v` to `w`, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I’m calling a “least Hamiltonian path.” I would think so, but I’m not sure.

Define the least Hamiltonian path from `v` to `w` to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider `K5` the graph with vertices `{1,2,3,4,5}` and all possible edges, then the least Hamiltonian path for `(v,w)` = `(2,3)` is `21453`. If you were at vertex 2, the next least vertex would be 1. Then, the next least vertex would 4. etc.

Therefore, my actual question is: Given graph `G` and vertices `v` and `w` can you non-deterministically walk the least Hamiltonian path from `v` to `w`, if it exists?

Motivation: If so, then perhaps there’s a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices `v` and `w`, and go through each pair of vertices such that `v<w`, checking for the existence of a least Hamiltonian path. To ensure all vertices in `G` are reached, keep a counter for the number of vertices walked (this should equal `N` if there are `N` vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from `v` to `w` will be unique, therefore it can be walked multiple times (each time you walk through it, starting at `v`, you’ll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated – one for the vertex you’re checking to see if it’s unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).

## Mean square displacement of self-avoiding walk in dimension 5 or more

What would be the best detailed written resource to study mean square displacement of self-avoiding walk in dimension 5 or more?

## Is there a flexible calculator available that can walk you through complex SQL licensing?

The basic license guide for Microsoft SQL Server is 40 pages in length. This document references still more documents on various topics, options, and definitions used for licensing. The license that one selects determines the conditions that will trigger additional costs required to stay functional over time.

Is there an accurate application that can be used to determine pricing for the various licensing and project a timeline for potential additional costs as a function of time and growth?

This would be a useful tool for proposal writers, legal teams, and planners.

It is very clear that licensing has become it’s own “career track” that favors large business.

A tool or business that could provide an unambiguous set of costs and terms based on list price could be free small to medium sized businesses to move forward on projects with some measure of confidence.

## Random walk generator – looking for optimizations (Python)

I just started learning Python and this is the first code I wrote. It’s a Random Walk generator. I think I got it to work pretty well but I’m also sure there are more effective and less clunky ways to do this. Could you give me some tips on what to change to make the code shorter/more optimized and just objectively more “pythonian” and better?

``````# Random Walk in two dimensions

import random

steps = "a"
maximal = "a"
minimal = "a"
Xstep = 0
Ystep = 0
StepSize = 0
PosNeg = 0

def new_line():
print(" ")

def invalid_enter_number():
print("Invalid input! Enter a number.")
new_line()

def invalid_enter_positive():
print("Invalid input! Enter a positive number.")
new_line()

new_line()
print("Random Walk in two dimensions")
new_line()

while type(steps) != int:
try:
steps = int(input("How many steps should be done? "))
while steps <= 0:
invalid_enter_positive()
steps = int(input("How many steps should be done? "))
except:
steps = ValueError
invalid_enter_number()
continue

while type(maximal) != int:
try:
maximal = int(input("How big is the biggest possible step? "))
while maximal <= 0:
invalid_enter_positive()
maximal = int(input("How big is the biggest possible step? "))
except:
maximal = ValueError
invalid_enter_number()
continue

if maximal != 1:
while type(minimal) != int:
try:
minimal = int(input("How big is the smallest possible step? "))
while minimal <= 0 or minimal >= maximal:
if minimal <= 0:
invalid_enter_positive()
minimal = int(input("How big is the smallest possible step? "))
else:
print("Number must be smaller than the biggest possible step!")
new_line()
minimal = int(input("How big is the smallest possible step? "))
except:
minimal = ValueError
invalid_enter_number()
continue
else:
minimal = 1

new_line()
print("Number of steps:", steps)

if maximal != 1:
print("Step size range:", minimal, "-", maximal)
else:
print("Step size: 1")

new_line()
print("Steps:")

while steps > 0:
StepSize = random.randint(minimal, maximal)
PosNeg = random.randint(0, 1)
chance = random.randint(0, 1)
if chance == 0 and PosNeg == 0:
Xstep += StepSize
elif chance == 0 and PosNeg == 1:
Xstep -= StepSize
elif chance == 1 and PosNeg == 0:
Ystep += StepSize
else:
Ystep -= StepSize
print("X:", Xstep, " Y:", Ystep)
steps -= 1

``````